Universität zu Köln

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.

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:	Creators Email ORCID ORCID Put Code Buchheim, Christoph UNSPECIFIED orcid.org/0000-0001-9974-404X UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
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