Logo

Login | Create Account

Detecting Symmetries by Branch & Cut

Buchheim, Christoph and Jünger, Michael (2002) Detecting Symmetries by Branch & Cut. [Conference Paper]

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
Classifications:G Algorithms and Complexity > G.910 Symmetries
P Styles > P.780 Symmetric
ID Code:491
Deposited By:Arnopolina, Galina
Deposited On:21 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=178

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.