Computing the independence number of intersection graphs
Computing the independence number of intersection graphs
复制标题
计算交图的独立数
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Pach
中科院分区：
文献类型：
--
作者：
J. Fox;J. Pach
计算几何对象集合中不相交元素的最大个数是计算几何中的一个经典问题，其应用范围从蜂窝网络中的频率分配到计算地图学中的地图标注。这个问题等价于找出通过将C的两个元素与一条边相连接而获得的交图的独立数α(G)，当且仅当它们的交集不为空时。即使对于平面上至多有两个不同坡度的线段系统来说，这也是一个NP-Hard任务。对于任意分段的系统，最著名的多项式时间近似算法是由Agarwal和Mustafa提出的，在最坏的情况下，它会返回<i><i>n</i><sup>1/2+<i>o</i>(1)</sup>-approximation</i>的α。利用Lipton-Tarjan分离子定理的推广，我们改进了这一结果，并给出了对于每个ε&>0，计算α(G<sup>C</sup>)的多项式时间算法，其逼近比至多为<i>n</i><sup>ε</sup>。相反，对于一般图，对于任何ε>；0，在因子<n</i><−ε</sup>内逼近独立数是NP-困难的。我们还给出了计算平面上弧形连通集的交图独立数的亚指数时间精确算法。
Computing the maximum number of disjoint elements in a collection <i>C</i> of geometric objects is a classical problem in computational geometry with applications ranging from frequency assignment in cellular networks to map labeling in computational cartography. The problem is equivalent to finding the independence number, <i>α</i>(<i>G</i><sub><i>C</i></sub>), of the intersection graph <i>G</i><sub><i>C</i></sub> of <i>C</i>, obtained by connecting two elements of <i>C</i> with an edge if and only if their intersection is nonempty. This is known to be an NP-hard task even for systems of segments in the plane with at most two different slopes. The best known polynomial time approximation algorithm for systems of arbitrary segments is due to Agarwal and Mustafa, and returns in the worst case an <i>n</i><sup>1/2+<i>o</i>(1)</sup>-approximation for <i>α</i>. Using extensions of the Lipton-Tarjan separator theorem, we improve this result and present, for every ε > 0, a polynomial time algorithm for computing α(<i>G</i><sub><i>C</i></sub>) with approximation ratio at most <i>n</i><sup>ε</sup>. In contrast, for general graphs, for any ε > 0 it is NP-hard to approximate the independence number within a factor of <i>n</i><sup>1−ε</sup>. We also give a subexponential time exact algorithm for computing the independence number of intersection graphs of arcwise connected sets in the plane.