Min-Max Multiway Cuts in Several Special Graphs
Xin Xiao · 2011
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.