Approximation Algorithms for Independent Sets in Map Graphs
Approximation Algorithms for Independent Sets in Map Graphs
复制标题
地图图中独立集的近似算法
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Zhi
中科院分区：
文献类型：
--
作者：
Zhi
本文给出了一个多项式时间逼近算法，用于计算给定映射图G中顶点有权或无权的最大独立集问题。如果G与映射一起给出，则无论G的每个顶点是否被赋权，对于任意给定的常数δ>；0，都可以在O(N2)时间内得到1+δ之比。在G不带图的情况下，如果没有给顶点赋权，则在O(N7)时间内可以达到4的比率，反之，在O(N7 Logn)时间内可以达到O(Logn)的比率。我们的算法设计背后是关于地图图的几个基本结果，这些结果可以用来设计地图图的着色和顶点覆盖的良好逼近算法，也可以应用于地图图的其他问题。
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.