《信息科学技术学术著作丛书》序

前言

第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  本章小结

参考文献

附录