| 摘要 | 第9-13页 |
| ABSTRACT | 第13-16页 |
| 第1章 绪论 | 第17-26页 |
| 1.1 研究背景 | 第17-19页 |
| 1.2 问题描述 | 第19-21页 |
| 1.3 研究现状 | 第21-24页 |
| 1.4 本文主要贡献 | 第24-25页 |
| 1.5 论文结构 | 第25-26页 |
| 第2章 预备知识 | 第26-40页 |
| 2.1 算法和计算复杂性简介 | 第26-29页 |
| 2.2 近似算法以及不可近似性 | 第29-36页 |
| 2.2.1 近似误差与近似性能比 | 第30-31页 |
| 2.2.2 不可近似性 | 第31-36页 |
| 2.2.2.1 从一个NPC问题做归约 | 第32-35页 |
| 2.2.2.2 保持近似性的归约 | 第35-36页 |
| 2.3 图的基本术语以及基本性质 | 第36-40页 |
| 第3章 路径覆盖问题的近似算法及其不可近似性 | 第40-62页 |
| 3.1 最大的路径覆盖的边的数目的上界 | 第40-49页 |
| 3.1.1 划分 | 第42-45页 |
| 3.1.2 新的上界 | 第45-49页 |
| 3.2 近似性能比是10/7的算法 | 第49-54页 |
| 3.3 性能分析 | 第54-59页 |
| 3.4 不可近似性 | 第59-62页 |
| 第4章 内部顶点最多的生成树问题的近似算法及其复杂性 | 第62-88页 |
| 4.1 一个图的生成树的内部顶点数目的上界 | 第62-64页 |
| 4.2 近似性能比是1.5的算法 | 第64-72页 |
| 4.2.1 图的修剪 | 第64-66页 |
| 4.2.2 算法及其性能分析 | 第66-72页 |
| 4.2.2.1 最大的圈-路径覆盖的重新构造 | 第67-70页 |
| 4.2.2.2 生成树的构建 | 第70-72页 |
| 4.3 近似性能比是4/3的算法 | 第72-85页 |
| 4.3.1 图的简化 | 第73-77页 |
| 4.3.2 算法及其性能分析 | 第77-85页 |
| 4.3.2.1 重新构造最大的圈-路径覆盖 | 第77-82页 |
| 4.3.2.2 生成树的组装 | 第82-85页 |
| 4.4 不可近似性 | 第85-88页 |
| 第5章 结论与展望 | 第88-90页 |
| 5.1 本文总结 | 第88-89页 |
| 5.2 研究展望 | 第89-90页 |
| 参考文献 | 第90-95页 |
| 致谢 | 第95-96页 |
| 攻读学位期间发表的学术论文目录 | 第96-97页 |
| 攻读学位期间参与科研项目情况 | 第97-98页 |
| 外文论文 | 第98-132页 |
| 附件 | 第132页 |