Detecting Symmetries by Branch & Cut (Journal Version)

Buchheim, Christoph and Jünger, Michael (2003) Detecting Symmetries by Branch & Cut (Journal Version).
Published in: Mathematical Programming B Vol. 98 (1-3). pp. 369-384.

Abstract

The NP-hard problem of finding symmetries in an abstract graph plays an important role in automatic graph drawing and other applications. In this paper, we present an exact algorithm for automorphism and symmetry detection based on the branch & cut technique. We introduce IP-models for these problems and investigate the structure of the corresponding polytopes. For automorphisms, a complete description of the polytope is derived from a given set of generators of the automorphism group. The rotation polytopes are shown to be related to the asymmetric traveling salesman polytope, while the reflection polytope is related to the matching polytope. The algorithm was implemented within the ABACUS-framework and proves to run fast in practice.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: No citation data.
Uncontrolled Keywords: symmetry integer programming branch-and-cut
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks

  • 20-XX Group theory and generalizations > 20Bxx Permutation groups > 20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Additional Information: Special Issue in Honor of Egon Balas
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2002-438
    Depositing User: Christoph Buchheim
    Date Deposited: 17 Mar 2004 00:00
    Last Modified: 24 Jun 2013 15:25
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/438