Journal of Graph Algorithms and Applications 2-layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
Journal of Graph Algorithms and Applications 2-layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
M. Jünger;Petra Mutzel
中科院分区：
文献类型：
--
作者：
M. Jünger;Petra Mutzel
我们提出了两层直线相交极小化问题的算法，能够计算出精确的最优解。我们的计算结果使我们得出这样的结论，即如果一个层是固定的，即使问题是NP-难的，也不需要算法，并且对于具有两个可变层的一般问题，可以计算出真正的最优解，其中较小的层包含多达15个节点。对于更大的情况下，迭代重心法原来是几个流行的算法，其性能，我们可以通过比较他们的结果，以最佳解决方案的选择方法。
We present algorithms for the two l a yer straightline crossing minimization problem that are able to compute exact optima. Our computational results lead us to the conclusion that there is no need for heuristics if one layer is xed, even though the problem is NP-hard, and that for the general problem with two v ariable layers, true optima can be computed for sparse instances in which the smaller layer contains up to 15 nodes. For bigger instances, the iterated barycenter method turns out to be the method of choice among several popular heuristics whose performance we could assess by comparing their results to optimum solutions.