Min-Max Multiway Cuts in Several Special Graphs
几类特殊图中的最小最大多路割

给定边具有正权的无向图，并指定若干个称为终端的顶点，最小最大多路割问题是要得到所有顶点的一个聚类，要求每个子类恰好包含一个终端，并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置，是传统多路割问题的一个变形。当给定无向图是树图时，这一问题已经是强NP难解的。对于链图和环图，给出了线性时间的精确算法，该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图，给出了(2-1/2k2)-近似算法，k表示终端的数目。