参数计算导论PDF电子书下载

第1章 导引 1

第2章 参数计算简介 5

2.1 NP完全理论 5

2.2固定参数可解 7

2.3固定参数不可解 8

2.4固定参数枚举 10

2.5参数化方法 10

2.6本章小结 12

第3章 核心化 13

3.1 NT定理 15

3.1.1基于最大匹配的NT算法 15

3.1.2基于线性规划的NT算法 18

3.2皇冠分解 19

3.2.1点覆盖与皇冠分解 21

3.2.2 P2-Packing与皇冠分解 23

3.3极值归纳技术 31

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

3.3.2边不相交三角形Packing 32

3.3.3最多内部节点生成树 34

3.4随机方法 36

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

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

3.5.2连通点覆盖问题的核 40

3.5.3边支配集 44

3.6核下界技术 45

3.6.1对偶性方法 46

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

3.6.3基于参数化规约 49

3.7本章小结 50

第4章 分支搜索法 51

4.1常规的分支搜索法 52

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

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

4.4基于组合的分支搜索法 60

4.5本章小结 64

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

5.1迭代压缩 65

5.1.1提出背景与技术要点 66

5.1.2典型应用与效率探讨 70

5.2局部贪婪 73

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

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

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

5.4本章小结 80

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

6.1随机方法种类及其应用 82

6.1.1基于划分的随机方法 83

6.1.2基于分块的随机方法 88

6.2确定化方法 89

6.2.1 （n，k）-Universal Set 89

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

6.3本章小结 93

第7章 彩色编码 94

7.1基本概念 95

7.2构造方法 95

7.2.1随机化构造方法 96

7.2.2确定化构造方法 98

7.3本章小结 114

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

8.1平面图上的核心化技术 116

8.1.1平面图的基本概念 116

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

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

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

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

8.3本章小结 127

第9章 固定参数枚举 129

9.1固定参数枚举理论 129

9.2基于分支搜索的枚举 130

9.3基于彩色编码的枚举 136

9.4基于递归压缩的枚举 141

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

9.4.2 FVS的固定参数枚举算法 153

9.5本章小结 155

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

10.1广义参数化近似算法 157

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

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

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

10.2标准参数化近似算法 162

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

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

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

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

10.3.1算法的基本思想 170

10.3.2算法的主要步骤 171

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

10.5本章小结 175

第11章 树分解及其应用 176

11.1树分解基本理论 176

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

11.3其他宽度参数 180

11.4树分解的应用 181

11.5本章小结 187

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

12.1单体型计算问题 188

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

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

12.4本章小结 226

参考文献 227

附录 234