A New Approach to Exact Crossing Minimization
A New Approach to Exact Crossing Minimization
复制标题
精确交叉最小化的新方法
DOI：
10.1007/978-3-540-87744-8_24
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
I. Bomze
中科院分区：
文献类型：
--
作者：
Markus Chimani;Petra Mutzel;I. Bomze
交叉数问题是在平面上画一个图时，求出所需的最小边交叉数。尽管这个问题是NP-难的，我们感兴趣的是实际有效的算法来解决这个问题的可证明的最优性。针对交叉数问题，提出了一种新的整数线性规划方法。前一个公式[4]必须将交叉数多面体转化为高维多面体。我们的方法的核心思想是直接考虑自然交叉数多面体和切割它与多个线性有序多面体。这导致一个更紧凑的公式，无论是在变量和约束条件。
我们描述了一个分支和切割算法，连同一个组合列生成方案，以解决交叉数问题，证明最优性。我们的实验表明，新的方法是更有效的比旧的，即使在考虑一个大大改进的版本的前配方（也在本文中）。这是第一次，我们能够解决交叉数高达37的图。
The crossing numberproblem is to find the smallest number of edge crossings necessary when drawing a graph into the plane. Eventhough the problem is NP-hard, we are interested in practically efficient algorithms to solve the problem to provable optimality. In this paper, we present a novel integer linear programming (ILP) formulation for the crossing number problem. The former formulation [4] had to transform the crossing number polytope into a higher-dimensional polytope. The key idea of our approach is to directly consider the natural crossing number polytope and cut it with multiple linear-ordering polytopes. This leads to a more compact formulation, both in terms of variables and constraints.
We describe a Branch-and-Cut algorithm, together with a combinatorial column generation scheme, in order to solve the crossing number problem to provable optimality. Our experiments show that the new approach is more effective than the old one, even when considering a heavily improved version of the former formulation (also presented in this paper). For the first time, we are able to solve graphs with a crossing number of up to 37.