无线网络中若干NP-难问题的参数算法
| 摘要 | 第1-7页 |
| ABSTRACT | 第7-12页 |
| 第一章 绪论 | 第12-18页 |
| ·研究背景 | 第12-14页 |
| ·研究内容 | 第14-16页 |
| ·研究意义 | 第16-17页 |
| ·全文结构 | 第17-18页 |
| 第二章 参数计算理论概述 | 第18-29页 |
| ·计算复杂性 | 第18-21页 |
| ·P vs NP | 第18页 |
| ·参数复杂性 | 第18-20页 |
| ·多变量参数复杂性 | 第20-21页 |
| ·参数算法设计技术 | 第21-28页 |
| ·核心化 | 第21-23页 |
| ·树分解和动态规划 | 第23-26页 |
| ·着色技术 | 第26-28页 |
| ·整数线性规划 | 第28页 |
| ·小结 | 第28-29页 |
| 第三章 最小能量组播路由的参数算法设计与实现 | 第29-49页 |
| ·引言 | 第29-30页 |
| ·相关工作 | 第30-31页 |
| ·模型和相关定义 | 第31-32页 |
| ·固定参数可解算法 | 第32-38页 |
| ·等价转换 | 第33-34页 |
| ·算法 | 第34-38页 |
| ·固定参数不可解结果 | 第38-41页 |
| ·模拟实验与分析 | 第41-48页 |
| ·模拟环境 | 第42-43页 |
| ·性能分析 | 第43-48页 |
| ·小结 | 第48-49页 |
| 第四章 平面图上连通支配集问题核上界改进 | 第49-72页 |
| ·引言 | 第49-50页 |
| ·相关术语 | 第50-52页 |
| ·规约和着色规则 | 第52-64页 |
| ·问题的核 | 第64-71页 |
| ·小结 | 第71-72页 |
| 第五章 最大生命周期目标覆盖参数复杂性分析 | 第72-86页 |
| ·引言 | 第72-73页 |
| ·相关工作 | 第73-74页 |
| ·模型和相关定义 | 第74-75页 |
| ·度受限图上的复杂性 | 第75-78页 |
| ·参数复杂性 | 第78-85页 |
| ·“与可解情况的距离”的参数复杂性 | 第78-80页 |
| ·“目标节点个数”的参数复杂性 | 第80-82页 |
| ·组合参数的参数复杂性 | 第82-85页 |
| ·小结 | 第85-86页 |
| 第六章 完全p-支配集的参数算法设计 | 第86-100页 |
| ·引言 | 第86-87页 |
| ·相关术语 | 第87页 |
| ·UDG上的NP复杂性 | 第87-89页 |
| ·UDG上的固定参数不可解 | 第89-93页 |
| ·平面图上的参数亚指数算法设计 | 第93-99页 |
| ·树分解 | 第94页 |
| ·动态规划 | 第94-99页 |
| ·小结 | 第99-100页 |
| 第七章 结论 | 第100-105页 |
| ·主要贡献和创新点 | 第100-102页 |
| ·展望 | 第102-105页 |
| 参考文献 | 第105-115页 |
| 致谢 | 第115-116页 |
| 攻读博士学位期间主要的研究成果 | 第116-117页 |
