若干个NP问题的特殊情况.pdf

福州大学学报990503 页码:1/4 福州大学学报 Journal of Fuzhou University 1999年 第27卷 第５期 No.５ Vol.271999 若干NP完全问题的特殊情形 王晓东 摘要:讨论了图算法中若干NP完全问题在所给的图是一棵树时的特殊情形.利用树结 构的前序编号表示法提出了解树的最大独立集问题、最小顶点覆盖问题和最小支配 集问题的线性时间算法.在渐近意义下这些算法都是最优算法. 关键词:图;树;NP完全问题;计算复杂性 中图分类号:TP3 文献标识码:A Some Special Cases of NP-Complete Problems WANG Xiao -dong (Department of Computer Science and Technology, Fuzhou University，Fujian Fuzhou 350002, China) Abstract: This paper discusses some special cases of NP-complete graph problems in which the given graph is a tree. By means of the pre-order labeling presentation of a tree, we present several linear time algorithms for graph problems on trees. These algorithms are all asymptotically optimal. Keywords: graphs; trees; NP-complete problems; time complexities １ 引言 在图上定义的许多组合优化问题是NP完全问题.这类问题属于较难解的问题， 至今没有找到多项式时间算法，也很可能根本没有多项式时间算法.遇到这类问题 时，通常从以下几个方面来考虑并寻求解决办法. 1)特殊情形：仔细分析所遇到的NP完全问题，研究具体实例的特殊性，考虑是 否必须在最一般的意义下来解此问题.也许可利用具体实例的特殊性，在特殊条件 下解此问题.许多NP完全问题在特殊情形下可以找到多项式时间算法.例如求图G的 最大团问题是NP完全问题，而在图G是平面图的情形下，该问题是多项式时间可解 的. 2)动态规划和分枝限界方法：对于许多NP完全问题来说，用动态规划和分枝限 界方法常可得到较高的解题效率. 3)概率分析：对于许多NP完全问题，其困难实例出现的概率很小,因此对这类 NP完全问题常可设计出平均性能很好的算法. 4)近似算法：通常可以设计出解NP完全问题的多项式时间近似算法，以近似解 来代替最优解. 5)启发式算法：在用别的方法都不能奏效时，也可以采用启发式算法来解NP完 全问题.这类方法根据具体问题的启发式有哪些信誉好的足球投注网站策略来求问题的解，在实际使用时可 能很有效，但有时很难说清它的道理. 本文考虑关于图的若干NP完全问题的特殊情形.当所给的图G是一棵树时，许多 NP完全问题可在多项式时间内求解.特别地，对于图G的最小顶点覆盖问题、最大独 立集问题和最小支配集问题等都是NP完全问题 〔1〕.而在图G是一棵树时，可以有效 地解决.本文利用树的前序编号为工具，提出解决上述问题的O(n)时间算法. file://E:\temp\noi\大学学报\若干NP完全问题的特殊情形.htm 01-7-9 福州大学学报990503 页码:2/4 2 树的前序标号表示法 给定一棵树T，在计算机中可以有多种表示方法 〔2〕.在图论算法中，树是作为 一般的图来表示的，通常采用邻接表表示法.针对所考