An Integer Programming Approach to Fuzzy Symmetry Detection

Buchheim, Christoph and J√ľnger, Michael (2004) An Integer Programming Approach to Fuzzy Symmetry Detection.
Published In: Graph drawing 11th International Symposium, GD 2003, Perugia, Italy, September 21 - 24, 2003 ; revised papers, Lecture Notes in Computer Science. 2912 Springer 2004, pp. 166-177.


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

Download: [img] Postscript - Preprinted Version
Download (205kB) | Preview
Download: [img] PDF - Preprinted Version
Download (210kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2003-455
Depositing User: Christoph Buchheim
Date Deposited: 17 Mar 2004 00:00
Last Modified: 12 Jan 2012 10:45