带测度函数的连通支配集问题及其近似算法

摘要

本文引入测度函数的概念，提出了带测度函数的连通支配集问题(CDS(F))，使得它具有更广的应用范围。文章给出了问题的形式定义，证明了它在几种情形下的NP完全性，并给出了多项式时间的近似算法，它的近似度为ln｜V｜+3，给出了一个不可近似下界。文章同时指出，对子不可近似性的结果，似乎还可以提高，也许从集合覆盖来规约是一个方向。

目录

文摘

英文文摘

第一章引言

第二章计算复杂性

2.1预备知识——O，o，Θ，ω，Ω

2.2 P语言

2.3 NP语言

2.4 NP完全问题和多项式时间规约

2.5优化问题

第三章近似算法-对NP难问题的妥协

3.1近似算法的衡量标准-近似度

3.1.1近似算法的紧致性

3.1.2 PTAS与FPTAS

3.2不可近似性

3.2.1 PCP定理

3.3对NP难问题的另一种妥协-参数复杂性(Parameterized Complexity)

第四章带测度函数的连通支配集问题

4.1一般的支配集问题

4.2带测度函数的连通支配集问题

4.2.1近似算法

4.2.2不可近似性

第五章结论与展望

5.1总结

5.2下一步工作

附录

参考文献

索引

致谢

论文独创性声明及使用授权声明