第1章 导引

第2章 参数计算简介

2.1 NP完全理论

2.2固定参数可解

2.3固定参数不可解

2.4固定参数枚举

2.5参数化方法

2.6本章小结

第3章 核心化

3.1 NT定理

3.1.1基于最大匹配的NT算法

3.1.2基于线性规划的NT算法

3.2皇冠分解

3.2.1点覆盖与皇冠分解

3.2.2 P2-Packing与皇冠分解

3.3极值归纳技术

3.3.1极值归纳技术的基本原理

3.3.2边不相交三角形Packing

3.3.3最多内部节点生成树

3.4随机方法

3.5基于低度点的核心化方法

3.5.1基于低度点核心化方法的基本思想

3.5.2连通点覆盖问题的核

3.5.3边支配集

3.6核下界技术

3.6.1对偶性方法

3.6.2基于复杂性理论假设的方法

3.6.3基于参数化规约

3.7本章小结

第4章 分支搜索法

4.1常规的分支搜索法

4.2基于隐含参数的分支搜索法

4.3核心化-分支交替搜索法

4.4基于组合的分支搜索法

4.5本章小结

第5章 迭代压缩和局部贪婪

5.1迭代压缩

5.1.1提出背景与技术要点

5.1.2典型应用与效率探讨

5.2局部贪婪

5.2.1基于极大解和目标解关系的局部贪婪

5.2.2基于k大小目标解求解k+1大小目标解的局部贪婪

5.3递归压缩和局部贪婪的运用

5.4本章小结

第6章 随机参数算法设计技术

6.1随机方法种类及其应用

6.1.1基于划分的随机方法

6.1.2基于分块的随机方法

6.2确定化方法

6.2.1 （n，k）-Universal Set

6.2.2 3-Set Packing随机算法的确定化

6.3本章小结

第7章 彩色编码

7.1基本概念

7.2构造方法

7.2.1随机化构造方法

7.2.2确定化构造方法

7.3本章小结

第8章 平面图参数算法设计技术

8.1平面图上的核心化技术

8.1.1平面图的基本概念

8.1.2区域分解技术的基本原理

8.2基于平面图的参数算法设计

8.2.1平面支配集问题的亚指数算法

8.2.2层状分割性质与平面图问题参数算法

8.3本章小结

第9章 固定参数枚举

9.1固定参数枚举理论

9.2基于分支搜索的枚举

9.3基于彩色编码的枚举

9.4基于递归压缩的枚举

9.4.1 FVS的固定参数枚举子过程

9.4.2 FVS的固定参数枚举算法

9.5本章小结

第10章 参数算法与近似算法

10.1广义参数化近似算法

10.1.1常数近似率广义参数化近似算法

10.1.2固定参数可解时间近似方案

10.1.3以近似性能1/ε作为参数的近似算法

10.2标准参数化近似算法

10.2.1常数近似率标准参数化近似算法

10.2.2函数近似率标准参数化近似算法

10.2.3固定参数可解问题的近似算法

10.3 3-D Matching计数问题的一种参数化随机近似算法

10.3.1算法的基本思想

10.3.2算法的主要步骤

10.4不存在参数化近似算法的问题

10.5本章小结

第11章 树分解及其应用

11.1树分解基本理论

11.2基于树分解的参数算法设计

11.3其他宽度参数

11.4树分解的应用

11.5本章小结

第12章 参数计算的实际应用

12.1单体型计算问题

12.2生物多叉系统发生树最大一致森林问题

12.3无线网络中延时受限的最小能量组播路由的参数算法研究

12.4本章小结

参考文献

附录