Detecting Symmetries by Branch & Cut (Extended Abstract)

Buchheim, Christoph and Jünger, Michael (2002) Detecting Symmetries by Branch & Cut (Extended Abstract).
Published In: Graph drawing : 9th international symposium, GD 2001, Vienna, Austria, September 23 - 26, 2001 ; revised papers, Lecture Notes in Computer Science. 2265 Springer 2002, pp. 496-498.

Abstract

We present a new approach for detecting automorphisms and symmetries of an arbitrary graph based on branch & cut. We derive an IP-model for this problem and have a first look on cutting planes and primal heuristics. The algorithm was implemented within the ABACUS-framework; its experimental runtimes are promising.


Actions:
Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: No citation data.
Uncontrolled Keywords: graph drawing symmetries integer programming
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

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

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • 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
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2001-422
    Depositing User: Christoph Buchheim
    Date Deposited: 23 Jun 2002 00:00
    Last Modified: 08 Jul 2013 08:33
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/422