An Integer Programming Approach to Fuzzy Symmetry Detection

Buchheim, Christoph and Jünger, Michael (2004) An Integer Programming Approach to Fuzzy Symmetry Detection. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 166-177 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_16).

Full text not available from this repository.

Abstract

The problem of exact symmetry detection in general graphs has received much attention recently. In spite of its NP-hardness, two different algorithms have been presented that in general can solve this problem quickly in practice [5,2]. However, as most graphs do not admit any exact symmetry at all, the much harder problem of fuzzy symmetry detection arises: a minimal number of certain modifications of the graph should be allowed in order to make it symmetric. We present a general approach to this problem: we allow arbitrary edge deletions and edge creations; every single modification can be given an individual weight. We apply integer programming techniques to solve this problem exactly or heuristically and give runtime results for a first implementation.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_16
Classifications:G Algorithms and Complexity > G.910 Symmetries
ID Code:447

Repository Staff Only: item control page

References

ABACUS - A Branch-And-CUt System. www.informatik.uni-koeln.de/abacus.

D. Abelson, S. Hong, and D. Taylor. A group-theoretic mwthod for drawing graphs symmetrically. In M. Goodrich and S. Kobourov, editors, Graph Drawing 2002, volume 2528 of LNCS, pages 86-97. Springer-Verlag, 2002.

C. Buchheim. An Integer Programming Approach to Exact and Fuzzy Symmetry Detection. PhD thesis, Institut für Informatik, Universität zu Köln, 2003. Available at kups.ub.uni-koeln.de/volltexte/2003/918.

C. Buchheim and M. Jünger. Detecting symmetries by branch & cut. In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing 2001, volume 2265 of Lecture Notes in Computer Science, pages 178-188. Springer-Verlag, 2002.

C. Buchheim and M. Jünger. Detecting symmetries by branch & cut. Mathematical Programming, Series B, 98:369-384, 2003.

H.-L. Chen, H.-I. Lu, and H.-C. Yen. On maximum symmetric subgraphs. In J. Marks, editor, Graph Drawing 2000, volume 1984 of LNCS, pages 372-383. Springer Verlag, 2001.

CPLEX 7.0. www.ilog.com/products/cplex.

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

S. Hong and P. Eades. Drawing planar graphs symmetrically II: Biconnected graphs. Technical Report CS-IVG-2001-01, University of Sydney, 2001.

S. Hong and P. Eades. Drawing planar graphs symmetrically III: Oneconnected graphs. Technical Report CS-IVG-2001-02, University of Sydney, 2001.

S. Hong and P. Eades. Drawing planar graphs symmetrically IV: Disconnected graphs. Technical Report CS-IVG-2001-03, University of Sydney, 2001.

S. Hong, B. McKay, and P. Eades. Symmetric drawings of triconnected planar graphs. In SODA 2002, pages 356-365, 2002.

J. Manning. Computational complexity of geometric symmetry detection in graphs. In N. Sherwani, E. de Doncker, and J. Kapenga, editors, First Great Lakes Computer Science Conference, volume 507 of LNCS, pages 1-7. Springer-Verlag, 1991.

H. Purchase. Which aesthetic has the gratest effect on human understanding? In G. Di Battista, editor, Graph Drawing '97, volume 1353 of LNCS, pages 248-261. Springer-Verlag, 1998.