【摘要】 Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*(︱（2l）～（1/2）︱^2l4^k)的参数化算法,其中,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）︱^2l4^k) 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）.更多还原