Approximation algorithms for NP-complete problems on planar graphs
Approximation algorithms for NP-complete problems on planar graphs
复制标题
DOI：
10.1145/174644.174650
复制
发表时间：
1983-11
期刊：
影响因子：
--
通讯作者：
B. S. Baker
中科院分区：
文献类型：
--
作者：
B. S. Baker
本文描述了一种通用技术，可用于获得平面图上各种 NP 完全问题的近似算法。该策略取决于将平面图分解为我们称为 k-outerplanar 形式的子图。对于固定的 k，感兴趣的问题可以通过动态规划在 k 外平面图上的线性时间内最优地解决。对于一般平面图，如果问题是最大化问题，例如最大独立集，则该技术为每个 k 给出一个线性时间算法，该算法产生大小至少为 (k-1)/k 最优的解。如果问题是最小化问题，例如最小顶点覆盖，它会为每个 k 给出一个线性时间算法，该算法产生的解决方案的大小最多为 (k + 1)/k 最优。采用 k = c log log n 或 k = c log n，其中 n 是节点数，c 是某个常数，我们得到多项式时间近似方案，即随着 n 的增加，解大小收敛到最优的算法。该方法提供近似方案的问题类别包括最大独立集、最大瓦片回收、划分为三角形、最大H匹配、最小顶点覆盖、最小支配集和最小边缘支配集。对于这些问题和某些其他问题，k 外平面图的可解性证明也扩大了已知问题可解的平面图类别。
This paper describes a general technique that can be used to obtain approximation algorithms for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form we call k- outerplanar. For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming. For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm that produces a solution whose size is at least (k-1)/k optimal. If the problem is a minimization problem, such as minimum vertex cover, it gives for each k a linear time algorithm that produces a solution whose size is at most (k + 1)/k optimal. Taking k = c log log n or k = c log n, where n is the number of nodes and c is some constant, we get polynomial time approximation schemes, i.e. algorithms whose solution sizes converge toward optimal as n increases. The class of problems for which this approach provides approximation schemes includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. For these and certain other problems, the proof of solvability on k-outerplanar graphs also enlarges the class of planar graphs for which the problems are known to be solvable.