欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
Multicut问题即在一个图上删除最少个数的顶点，使得预先给定的一组顶点对均不连通．该问题是NP难的．在深入分析问题结构特点的基础上，运用集合划分策略和相关问题的最新研究结果，对它提出了一种时间复杂度为O^＊（┌√21^┐214^k）的参数化算法，其中，l为给定的顶点对数目，k为需删除的顶点个数．该算法明显改进了当前时间复杂度为O^＊（2^klk^k4^k^3）的最好算法.
英文摘要：
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^＊（┌√21^┐214^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^klk^k4^k^3）.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：