%0 Journal Article
%T multicut问题参数算法的改进
%A 刘运龙？
%A 王建新？
%A 陈建二？
%J 软件学报
%P 1515-1523
%D 2010
%X multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是np难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为o*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为o*的最好算法.
%K muliticut
%K node
%K multicut
%K 集合划分
%K 极大恰当划分
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3625&flag=1