Computer Science ›› 2011, Vol. 38 ›› Issue (7): 216-219.
Previous Articles Next Articles
LI Shu-guang,XIN Xiao
Online:
Published:
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
LI Shu-guang,XIN Xiao. Min-Max Multiway Cuts in Several Special Graphs[J].Computer Science, 2011, 38(7): 216-219.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2011/V38/I7/216
Cited