节点文献
Multicut问题参数算法的改进
Improved Parameterized Algorithm for the Multicut Problem
【摘要】 Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*(︱(2l)~(1/2)︱2l4k)的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*(2klkk4k3)的最好算法.
【Abstract】 The Multicut problem is for a given graph and a given collection of terminal pairs to find a vertex set of minimum size such that the two terminals in any pair are not connected after deletion of this vertex set.This problem is NP-hard.Based on the deep analysis of its structural characteristics,employing the strategy of set partition and the improved results of another related problem,this paper proposes a parameterized algorithm of running time O*(︱(2l)~(1/2)︱2l4k) for the problem,in which l denotes the number of terminal pairs and k denotes the number of removed vertices.This algorithm significantly improves the previous one of running time O*(2 kl kk 4k3).
【Key words】 Muliticut; Node Multicut; set partition; maximal proper partition;
- 【文献出处】 软件学报 ,Journal of Software , 编辑部邮箱 ,2010年07期
- 【分类号】TP301.6
- 【被引频次】3
- 【下载频次】141