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 , pp. 166-177(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item