Buchheim, Christoph ORCID: 0000-0001-9974-404X, Chimani, Markus, Ebner, Dietmar, Gutwenger, Carsten, Klau, Gunnar W., Mutzel, Petra ORCID: 0000-0001-7621-971X and Weiskircher, René (2008). A branch-and-cut approach to the crossing number problem. Discrete optimization, 5 (2). pp. 373-388. Elsevier.

[img]
Preview
PDF
zaik2006-508.pdf - Submitted Version

Download (430kB) | Preview

Abstract

The crossing number of a graph is the minimum number of edge crossings in any drawing of the graph in the plane. Extensive research has produced bounds on the crossing number and exact formulae for special graph classes, yet the crossing numbers of graphs such as K_{11} or K_{9,11} are still unknown. Finding the crossing number is NP-hard for general graphs and no practical algorithm for its computation has been published so far. We present an integer linear programming formulation that is based on a reduction of the general problem to a restricted version of the crossing number problem in which each edge may be crossed at most once. We also present cutting plane generation heuristics and a column generation scheme. As we demonstrate in a computational study, a branch-and-cut algorithm based on these techniques as well as recently published preprocessing algorithms can be used to successfully compute the crossing number for small to medium sized general graphs.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Buchheim, ChristophUNSPECIFIEDorcid.org/0000-0001-9974-404XUNSPECIFIED
Chimani, MarkusUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Ebner, DietmarUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Gutwenger, CarstenUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Klau, Gunnar W.UNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
Weiskircher, RenéUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548911
Journal or Publication Title: Discrete optimization
Volume: 5
Number: 2
Page Range: pp. 373-388
Date: 2008
Publisher: Elsevier
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/54891

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item