关键词: 最小最大多路割，链图，环图，树图，限制树宽图

Abstract: 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 minimizcd,where the cost of a cluster is defined as the total edge weight at the boundary of the cluster. I}his 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“·the number of terminals.

Key words: Min-max multiway cuts,Chains,Rings,Trees,Graphs of bounded treewidth