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

Min-Max Multiway Cuts in Several Special Graphs

作　　者：李曙光[1,2] 辛晓[3] 

机构地区：[1]山东工商学院计算机科学与技术学院,烟台264005 [2]山东大学计算机科学与技术学院,济南250101 [3]山东工商学院外国语学院,烟台264005

出　　处：《计算机科学》2011年第7期216-219,共4页Computer Science

基　　金：国家自然科学基金(60970105);山东省信息产业发展专项资金项目(2008X00039);山东省软科学研究计划(2010RKE20029)资助

摘　　要：给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强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.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]