Detecting almost symmetries of graphs

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ben KnuevenORCiD, Jim OstrowskiORCiD, Sebastian Pokutta
DOI:https://doi.org/10.1007/s12532-017-0124-3
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2017
Tag:Software; Theoretical Computer Science
Volume:10
Issue:2
Page Number:43
First Page:143
Last Page:185
Mathematical Programming Computation :MPC 2018 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.