An Integer Programming Approach to Fuzzy Symmetry DetectionBuchheim, Christoph and Jünger, Michael (2004) An Integer Programming Approach to Fuzzy Symmetry Detection. In: Graph Drawing 11th International Symposium, GD 2003, September 2124, 2003 , pp. 166177(Official URL: http://dx.doi.org/10.1007/9783540245957_16). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540245957_16
AbstractThe problem of exact symmetry detection in general graphs has received much attention recently. In spite of its NPhardness, 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.
Actions (login required)
