%0 Journal Article
%T Improved Parameterized Algorithm for the Multicut Problem<br>Multicut问题参数算法的改进
%A LIU Yun-Long
%A WANG Jian-Xin
%A CHEN Jian-Er
%A <br>刘运龙
%A 王建新
%A 陈建二
%J 计算机系统应用
%D 2010
%I 
%X 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* 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*.
%K Muliticut
%K Node Multicut
%K set partition
%K maximal proper partition<br>Muliticut
%K Node
%K Multicut
%K 集合划分
%K 极大恰当划分
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=D4F6864C950C88FFCE5B6C948A639E39&aid=3B09D2A8DAB38FFB95CDA2C885B54BD9&yid=140ECF96957D60B2&vid=2A8D03AD8076A2E3&iid=DF92D298D3FF1E6E&sid=6F185A924223F19E&eid=777A6C995272142B&journal_id=1003-3254&journal_name=计算机系统应用&referenced_num=0&reference_num=11