A branch-and-cut approach to the crossing number problem

A branch-and-cut approach to the crossing number problem

0.00 Avg rating0 Votes
Article ID: iaor20091331
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 373
End Page Number: 388
Publication Date: May 2008
Journal: Discrete Optimization
Authors: , , , , , , ,
Keywords: programming: branch and bound
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 K11 or K9,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 for the first time.

Reviews

Required fields are marked *. Your email address will not be published.