几类特殊图中的最小最大多路割

Min-Max Multiway Cuts in Several Special Graphs

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

Given an undirected graph with positive edge weights and a subset of verticescalled terminals,the min-max multiway cut problem is to partition the vertices into clusters such that each cluster contains exactly one terminal and the maximum cost among the clusters is minimized,where the cost of a cluster is defined as the total edge weight at the boundary of the cluster.This problem is motivated by data plcacement in Peer-to-Peer networks and is a variant of the traditional multiway cut problem.It is strongly NP-hard even when the graph is a tree.For chains and rings,linear time exact algorithms were presented which minimize simultaneously both maximum cost and total cost of the clusters.For trees and graphs of bounded treewidth,a（2-1 2k2）-approximation algorithm was presented where k is the number of terminals.