本书较全面的介绍了参数计算理论的提出背景、理论范畴、相关算法设计与分析技术以及参数计算的实际应用。具体来说，本书通过应用实例阐述了核心化技术、局部贪婪、递归压缩、分支搜索、随机方法、彩色编码和固定参数枚举技术。本书还介绍了平面图上的相关算法设计和分析技术、核心化技术等等，并从生物信息计算角度探讨了参数计算理论的实际工程应用价值
样章试读
目录
《信息科学技术学术著作丛书》序
前言
第1章导引1
第2章参数计算简介5
2.1NP完全理论5
2.2固定参数可解7
2.3固定参数不可解8
2.4固定参数枚举10
2.5参数化方法10
2.6本章小结12
第3章核心化13
3.1NT定理15
3.1.1基于最大匹配的NT算法15
3.1.2基于线性规划的NT算法18
3.2皇冠分解19
3.2.1点覆盖与皇冠分解21
3.2.2P2?Packing与皇冠分解23
3.3极值归纳技术31
3.3.1极值归纳技术的基本原理31
3.3.2边不相交三角形Packing32
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 Set89
6.2.23?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.1FVS的固定参数枚举子过程143
9.4.2FVS的固定参数枚举算法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.33?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]]>
京公网安备 11010102004214号