An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
An Efficient Fixed Parameter Tractable Algorithm for
1-Sided Crossing Minimization
复制标题
一种有效的单边交叉最小化固定参数易处理算法
DOI：
10.1007/s00453-004-1093-2
复制
发表时间：
2002
期刊：
影响因子：
1.1
通讯作者：
S. Whitesides
中科院分区：
文献类型：
--
作者：
V. Dujmović;S. Whitesides
摘要
我们给出了一个O（φk · n2）固定参数的易处理算法
1-交叉口最小化。运行时间中的常数φ就是黄金分割比
φ =（1+ φ 5）/2 φ 1.618。常数k是函数的参数。
问题：允许的边缘交叉数。
Abstract
We give an O(φk · n2) fixed parameter tractable algorithm for the
1-Sided Crossing Minimization. The constant φ in the running time is the golden ratio
φ = (1+√5)/2 ≈ 1.618. The constant k is the parameter of the
problem: the number of allowed edge crossings.