%0 Journal Article
%T Min-Max Multiway Cuts in Several Special Graphs<br>几类特殊图中的最小最大多路割
%A LI Shu-guang
%A XIN Xiao
%A <br>李曙光
%A 辛晓
%J 计算机科学
%D 2011
%I 
%X 给定边具有正权的无向图，并指定若干个称为终端的顶点，最小最大多路割问题是要得到所有顶点的一个聚类，要求每个子类恰好包含一个终端，并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置，是传统多路割问题的一个变形。当给定无向图是树图时，这一问题已经是强NP难解的。对于链图和环图，给出了线性时间的精确算法，该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图，给出了(2-1/2k2)-近似算法，k表示终端的数目。
%K Min-max multiway cuts
%K Chains
%K Rings
%K Trees
%K Graphs of bounded treewidth<br>最小最大多路割，链图，环图，树图，限制树宽图
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=A02D22894B6747148662B4D0893DBAC5&yid=9377ED8094509821&vid=16D8618C6164A3ED&iid=DF92D298D3FF1E6E&sid=CEC789B3C68C3BB3&eid=D5C73DEF4CF8FAF3&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=15