| 几类特殊图中的最小最大多路割 |
| |
| 引用本文： | 李曙光,辛晓.几类特殊图中的最小最大多路割[J].计算机科学,2011,38(7):216-219. |
| |
| 作者姓名： | 李曙光 辛晓 |
| |
| 作者单位： | 1. 山东工商学院计算机科学与技术学院,烟台264005;山东大学计算机科学与技术学院,济南250101
2. 山东工商学院外国语学院,烟台,264005 |
| |
| 基金项目： | 本文受国家自然科学基金(60970105)，山东省信息产业发展专项资金项目(2008X00039)，山东省软科学研究计划(2010RKE20029)资助. |
| |
| 摘 要： | 给定边具有正权的无向图，并指定若干个称为终端的顶点，最小最大多路割问题是要得到所有顶点的一个聚类，要求每个子类恰好包含一个终端，并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置，是传统多路割问题的一个变形。当给定无向图是树图时，这一问题已经是强NP难解的。对于链图和环图，给出了线性时间的精确算法，该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图，给出了(2-1/2k2)-近似算法，k表示终端的数目。
|
| 关 键 词： | 最小最大多路割，链图，环图，树图，限制树宽图 |
Min-Max Multiway Cuts in Several Special Graphs |
| |
| LI Shu-guang,XIN Xiao.Min-Max Multiway Cuts in Several Special Graphs[J].Computer Science,2011,38(7):216-219. |
| |
| Authors: | LI Shu-guang XIN Xiao |
| |
| Affiliation: | (College of Computer Science and Tethnology, Shandong Institute of Business and Technology, Yantai 264005 , China);(School of Computer Science and Technology,Shandong University,Jinan 250101,China);(College of Foreign Studies,Shandong Institute of Business and Technology,Yantai 264005,China) |
| |
| Abstract: | |
| |
| Keywords: | Min-max multiway cuts Chains Rings Trees Graphs of bounded treewidth |
| 本文献已被 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
