关于一些网络最优化问题的近似算法的研究
| 摘要 | 第1-6页 |
| ABSTRACT(英文摘要) | 第6-11页 |
| 第一章 引言 | 第11-21页 |
| ·图论的基本概念和记号 | 第11-13页 |
| ·计算复杂度理论简介 | 第13-15页 |
| ·近似算法简介 | 第15-16页 |
| ·本文的主要结果 | 第16-21页 |
| ·Selected-interna斯坦纳树 | 第17页 |
| ·顶点赋权斯坦纳树 | 第17页 |
| ·顶点赋权斯坦纳树的PTAS | 第17页 |
| ·MIS与MCDS的关系及比值上界 | 第17-18页 |
| ·d-hop连通控制集 | 第18页 |
| ·赋权连通控制集 | 第18-19页 |
| ·单位圆球图上的连通控制集 | 第19-21页 |
| 第二章 斯坦纳树 | 第21-45页 |
| ·引言 | 第21-22页 |
| ·Selected-internal斯坦纳树 | 第22-30页 |
| ·构造斯坦纳树T′ | 第23-25页 |
| ·修正T′到T″ | 第25-29页 |
| ·还原T″中的v_(T_i)并得到结果 | 第29-30页 |
| ·顶点赋权斯坦纳树 | 第30-36页 |
| ·最小支撑树方法 | 第31-34页 |
| ·2.5ρ近似算法 | 第34-36页 |
| ·顶点赋权斯坦纳树的PTAS | 第36-45页 |
| ·PTAS算法的基本策略 | 第37-39页 |
| ·PTAS算法的详细描述 | 第39-41页 |
| ·近似比分析 | 第41-45页 |
| 第三章 连通控制集 | 第45-79页 |
| ·引言 | 第45-46页 |
| ·MIS与MCDS的关系及比值上界 | 第46-59页 |
| ·MIS与MCDS的具体联系方法 | 第47-49页 |
| ·Voronoi图 | 第49-54页 |
| ·计算新的上界 | 第54-58页 |
| ·小结与讨论 | 第58-59页 |
| ·d-hop连通控制集 | 第59-71页 |
| ·预备知识 | 第61-62页 |
| ·TCDS算法 | 第62-64页 |
| ·近似比分析 | 第64-68页 |
| ·算法的推广:d-CDS算法 | 第68-70页 |
| ·小结与讨论 | 第70-71页 |
| ·赋权连通控制集 | 第71-73页 |
| ·单位圆球图上的连通控制集 | 第73-76页 |
| ·贪心算法 | 第73-76页 |
| ·小节与讨论 | 第76页 |
| ·总结与后续工作 | 第76-79页 |
| 参考文献 | 第79-87页 |
| 在读期间完成的主要论文 | 第87-89页 |
| 致谢 | 第89页 |
