算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第11章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第11章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章参数化算法顶点覆盖问题的参数化算法反馈集问题的参数化算法支配集问题的参数化算法参数化的计算复杂性框架参数化算法NP完全问题：很难在短时间内求出问题的精确解近似算法：在可接受的时间内求出问题的近似解参数化算法：在特定的参数范围内对问题进行精确求解11.1顶点覆盖问题的参数化算法顶点覆盖问题输入：一个无向图G=输出：G的最小顶点覆盖C，其满足

2、C

3、=(MinV′:V′V((u,v)E:uV′vV′):

4、V′

5、)abcdfe11.1顶点覆盖问题的参数化算法参数化顶点覆盖问题输入：一个无向图G=和一个整数k输出：G中大小不超过k的一个顶点覆盖

6、，不存在则返回空集abcdfe11.1顶点覆盖问题的参数化算法参数化顶点覆盖问题搜索树方法：每次任选一条边(u,v)，从原问题分化出两个子节点：G{u}（u加入顶点覆盖）和G{v}（v加入顶点覆盖），直至子图中不包含任何边abcdfebcdfeacdfebcdfeacdfecdfebdfedfecfefedfcfdfebfebfbcdfeacdfeadfeacdfafeadfaeaf11.1顶点覆盖问题的参数化算法参数化顶点覆盖问题AlgorithmSearch_VertexCover(G:Graph,k:int)beginleti=0,P={(,G)};while(i

7、中，如果某个顶点vV的度数大于k，那么G的任何一个k-顶点覆盖都必然包含v【定理11.2】若G′中边的

8、数量大于kk′，则G′中不存在k′-顶点覆盖当G′中边的数量不大于kk′时，其顶点数量

9、V′

10、2kk′2k2，搜索树算法的时间不超过O(2kk2)将P(G,k)简约到P(G′,k′)的时间不超过O(kn)，因此参数化算法的时间复杂度为O(kn+2kk2)11.1顶点覆盖问题的参数化算法增强的问题简约与搜索树方法R0：图中的孤立顶点（度数为0）均可以直接删除R1：若顶点v的度数为1，则将其相邻顶点u加入到最小顶点覆盖C中，P(G,k)简约为P(G{v,u},k−1)R2：若顶点v的度数为2，且它的两个相邻顶点u1和u2之间有边相连，则将u1和u2都加入到最小顶点覆盖C中，

11、P(G,k)简约为P(G{v,u1,u2},k−2)11.1顶点覆盖问题的参数化算法增强的问题简约与搜索树方法R3：若顶点v的度数为2，且它的两个相邻顶点u1和u2之间无边相连。此时要么将{u1,u2}加入到顶点覆盖C中，子节点上的子图为G{u1,u2}；要么将u1和u2的所有邻接顶点（包括v）加入到C中，子节点上的子图为G(N(u1)N(u2))。这样当前节点分化出两个下层节点R4：若顶点v的度数大于等于5，则要么将v加入到C中，要么将v的所有邻接顶点加入到C中，这样当前节点也分化出两个下层节点，子节点上的子图中删去相应的顶点和相关边11.1顶点覆盖问题的参数化算法

12、增强的问题简约与搜索树方法R5：若顶点v的度数为3，其相邻顶点为u1,u2和u3：R5.1：若两个相邻顶点u1和u2之间有边相连，则要么将{u1,u2,u3}加入到C中，要么将u3的所有邻接顶点加入到C中。R5.2：若u1,u2和u3还有另一个公共的邻接顶点v′，则要么将{u1,u2,u3}加入到C中，要么将{v,v′}加入到C中。R5.3：若u1,u2和u3相互之间无边相连，且u1除了v之外还有至少3个邻接顶点。此时要么将{u1,u2,u3}加入到C中，要么将u1的所有邻接顶点加入到C中，要么将{u1}N(u2)N(u3)加入到C中。R5.4：若u1,u2和u3相互之间

13、无边相连，且它们除了v之外各自还有2个邻接顶点。不妨设u1的另两个邻接顶点是v′和v′′，此时要么将{u1,u2,u3}加入到C中，要么将{v,v′,v′′}加入到C中，要么将N(u2)N(u3)N(v′)N(v′′)加入到C中。11.1顶点覆盖问题的参数化算法增强的问题简约与搜索树方法R6：若顶点v的度数为4，其相邻顶点为u1,u2,u3和u4：R6.1：若某两个相邻顶点（假设是u1和u2）之间有边相连，则要么将{u1,u2,u3,u4}加入到C中，要么将N(u3)加入到C中，要么将{u3}N