Buchheim, Christoph ORCID: 0000-0001-9974-404X and Jünger, Michael (2004). An Integer Programming Approach to Fuzzy Symmetry Detection. In: Graph drawing 11th International Symposium, GD 2003, Perugia, Italy, September 21 - 24, 2003 ; revised papers, pp. 166-177. Springer.

[img]
Preview
PDF
zaik2003-455.pdf - Draft Version

Download (210kB) | Preview

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. 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: Book Section, Proceedings Item or annotation in a legal commentary
Creators:
CreatorsEmailORCIDORCID Put Code
Buchheim, ChristophUNSPECIFIEDorcid.org/0000-0001-9974-404XUNSPECIFIED
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548746
Title of Book: Graph drawing 11th International Symposium, GD 2003, Perugia, Italy, September 21 - 24, 2003 ; revised papers
Series Name: Lecture Notes in Computer Science
Volume: 2912
Page Range: pp. 166-177
Date: 2004
Publisher: Springer
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54874

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item