Detecting Symmetries by Branch & Cut

Buchheim, Christoph and Jünger, Michael (2002) Detecting Symmetries by Branch & Cut. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 178-188 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_15).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_15
Classifications:G Algorithms and Complexity > G.910 Symmetries
P Styles > P.780 Symmetric
ID Code:491

Repository Staff Only: item control page

References

O. Bastert. New ideas for canonically computing graph algebras. Technical Report TUM-M9803, Technische Universität München, Fakultät für Mathematik, 1998.

P. Eades and X. Lin. Spring algorithms and symmetry. Theoretical Computer Science, 240(2):379-405.

H. de Fraysseix. A heuristic for graph symmetry detection. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci., pages 276-285, Berlin. Springer, 1999.

S.-H. Hong, P. Eades, and S.-H. Lee. Finding planar geometric automorphisms in planar graphs. In K.-Y. Chwa and O. H. Ibarra, editors, Proc. Algorithms and Computation (ISAAC '98), volume 1533 of Lecture Notes in Comput. Sci., pages 277-286, Berlin, 1998. Springer.

M. Jünger and S. Thienel. The ABACUS system for branch-and-cut-and-price-algorithms in integer programming and combinatorial optimization. Software Practice & Experience, 30(11):1325-1352, 2000.

J. Manning. Computational complexity of geometric symmetry detection in graphs. Computing in the 90's (Kalamazoo, MI, 1989), vol. 507 of LNCS, Springer-Verlag, pp. 1-7, 1991.

H. Purchase. Which aesthetichas the greatest effect on human understanding? In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 248-261. Springer Verlag, 1997.

R. Read and D. Corneil. The graph isomorphism disease. Journal of Graph Theory, 1:339-363, 1977.

The Rome library of undirected graphs. Available at: www.inf.uniroma3.it/people/gdb/wp12/undirected-1.tar.gz