| 中文部分 | 第1-80页 |
| 中文摘要 | 第6-10页 |
| 英文摘要 | 第10-15页 |
| 符号索引 | 第15-16页 |
| 第一章.前沿 | 第16-23页 |
| §1.1 研究背景:基于波分复用技术的全光网络 | 第16-17页 |
| §1.2 算法的一些关键定义 | 第17-18页 |
| §1.3 WDM网络中的几个优化问题 | 第18-20页 |
| §1.3.1 波长分配和路染色问题 | 第19页 |
| §1.3.2 波长转换问题 | 第19页 |
| §1.3.3 请求排序问题 | 第19-20页 |
| §1.3.4 环负载问题 | 第20页 |
| §1.4 一些优化问题的相关结论 | 第20-21页 |
| §1.5 有向图的一些相关问题 | 第21-23页 |
| §1.5.1 强连通图的强连通性 | 第21-22页 |
| §1.5.2 最小直径定向问题 | 第22-23页 |
| 第二章.超图嵌入问题的一些PTAS算法 | 第23-45页 |
| §2.1 引言 | 第23-24页 |
| §2.2 MCHEC问题的来源以及一些相关的结论 | 第24页 |
| §2.3 MCHEC问题的一个PTAS算法 | 第24-35页 |
| §2.3.1 算法的思想 | 第26-27页 |
| §2.3.2 嵌入下标在R_(i_1,i_2,…,i_r)中的超边 | 第27-28页 |
| §2.3.3 完成下标在U_(i_1,i_2,…,i_r)中的超边的嵌入 | 第28-35页 |
| §2.4 应用 | 第35-44页 |
| §2.4.1 超图在树环中的嵌入问题 | 第35-40页 |
| §2.4.2 超图在环圈中的嵌入问题 | 第40-44页 |
| §2.5 总结 | 第44-45页 |
| 第三章.WDHEC问题的一个2-近似算法 | 第45-56页 |
| §3.1 引言 | 第45-46页 |
| §3.2 简介 | 第46-48页 |
| §3.3 WDHEC问题的NP-完备性 | 第48-51页 |
| §3.4 WDHEC问题的算法 | 第51-52页 |
| §3.5 相关问题-WDHETR问题的算法 | 第52-55页 |
| §3.6 总结 | 第55-56页 |
| 第四章.强竞赛图的强连通性 | 第56-62页 |
| §4.1 引言 | 第56页 |
| §4.2 简介 | 第56页 |
| §4.3 强竞赛图的强连通性 | 第56-60页 |
| §4.4 Moon定理的一个证明 | 第60-61页 |
| §4.5 总结 | 第61-62页 |
| 第五章.Split完全图的最小直径定向问题 | 第62-69页 |
| §5.1 引言 | 第62-63页 |
| §5.2 简介 | 第63-64页 |
| §5.3 split完全图的最小直径定向 | 第64-68页 |
| §5.4 总结 | 第68-69页 |
| 参考文献 | 第69-77页 |
| 致谢 | 第77-78页 |
| 作者简介 | 第78-79页 |
| 学位论文评阅及答辩情况表 | 第79-80页 |
| 英文部分 | 第80-171页 |
| Chinese abstract | 第86-90页 |
| English abstract | 第90-95页 |
| Notation index | 第95-96页 |
| Chapter 1. Introduction | 第96-106页 |
| §1.1 Motivation: The WDM networks | 第96-97页 |
| §1.2 Some key concepts of algorithms | 第97-99页 |
| §1.3 Some optimization problems of the WDM networks | 第99-102页 |
| §1.3.1 Wavelength assignment and path coloring | 第99-100页 |
| §1.3.2 Wavelength conversion | 第100-101页 |
| §1.3.3 Call scheduling | 第101页 |
| §1.3.4 Ring loading | 第101-102页 |
| §1.4 Related work of some optimization problems | 第102-103页 |
| §1.5 Some problems of graph theory | 第103-106页 |
| §1.5.1 Strong connectivity of strong tournaments | 第103-104页 |
| §1.5.2 The problem of minimal diameter orientation | 第104-106页 |
| Chapter 2. PTAS for hypergraph embedding problems | 第106-133页 |
| §2.1 Introduction | 第106-107页 |
| §2.2 Derivation of the MCHEC problem and related results | 第107-108页 |
| §2.3 A PTAS for the MCHEC problem | 第108-121页 |
| §2.3.1 Idea of the algorithm | 第110-112页 |
| §2.3.2 Embedding hyperedges with index in R_(i_1,i_2,...,i_r) | 第112-114页 |
| §2.3.3 Finish embedding hyperedges with index in U_(i_1,i_2,...,i_r) | 第114-121页 |
| §2.4 Application | 第121-132页 |
| §2.4.1 Embedding hypergraph in a trees of rings | 第121-127页 |
| §2.4.2 Embedding hypergraph in a rings cycle | 第127-132页 |
| §2.5 Conclusion | 第132-133页 |
| Chapter 3. A 2-approximation algorithm for the WDHEC problem | 第133-146页 |
| §3.1 Introduction | 第133-135页 |
| §3.2 Preliminaries | 第135-137页 |
| §3.3 NP-completeness of the WDHEC problem | 第137-140页 |
| §3.4 Algorithm for the WDHEC problem | 第140-142页 |
| §3.5 A related work-algorithm for the WDHETR problem | 第142-145页 |
| §3.6 Conclusion | 第145-146页 |
| Chapter 4. A new strong connectivity of strong tournaments | 第146-153页 |
| §4.1 Introduction | 第146页 |
| §4.2 Preliminaries | 第146-147页 |
| §4.3 Strong connectivity of strong tournaments | 第147-151页 |
| §4.4 Another proof of Moon Theorem | 第151-152页 |
| §4.5 Conclusion | 第152-153页 |
| Chapter 5. Minimal diameter orientation of special split graphs | 第153-161页 |
| §5.1 Introduction | 第153-154页 |
| §5.2 Preliminaries | 第154-156页 |
| §5.3 Minimal diameter orientation of complete split graphs | 第156-160页 |
| §5.4 Conclusion | 第160-161页 |
| Bibliography | 第161-169页 |
| Acknowledgements | 第169-170页 |
| Curriculum Vitae | 第170-171页 |
| 学位论文评阅及答辩情况表 | 第171页 |
