Name
Abstract | ||
|---|---|---|
We present a branch-and-bound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that minimizes the number of vertex orbits. We call the symmetries on such a subgraph “almost symmetries” of G. We implement our branch-and-bound framework in PEBBL to allow for parallel enumeration and demonstrate good scaling up to 16 cores. We show that the presented branching strategy is much better than a random branching strategy on the tested graphs. Finally, we consider the presented strategy as a heuristic for quickly finding almost symmetries of a graph G. The software that was reviewed as part of this submission has been issued the Digital Object Identifier DOI: 10.5281/zenodo.840558. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s12532-017-0124-3 | Math. Program. Comput. |
Keywords | Field | DocType |
Almost symmetries,Graph automorphism,Branch-and-bound,05C60,05C85,90C27 | Integer,Graph automorphism,Discrete mathematics,Mathematical optimization,Combinatorics,Heuristic,Circulant graph,Branch and bound,Vertex (geometry),Graph factorization,Mathematics,Homogeneous space | Journal |
Volume | Issue | ISSN |
10 | 2 | 1867-2949 |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ben Knueven | 1 | 0 | 0.34 |
| Jim Ostrowski | 2 | 2 | 1.10 |
| Sebastian Pokutta | 3 | 267 | 32.02 |