| 参数为k的几乎树中的染色多路割 |
| |
| 引用本文： | 李曙光,辛晓.参数为k的几乎树中的染色多路割[J].计算机科学,2010,37(2):246-249. |
| |
| 作者姓名： | 李曙光 辛晓 |
| |
| 作者单位： | 1. 山东工商学院计算机科学与技术学院,烟台,264005
2. 山东工商学院外国语学院,烟台,264005 |
| |
| 基金项目： | 国家自然科学基金(60673153,60970105);;山东省信息产业发展专项资金项目(2008X00039)资助 |
| |
| 摘 要： | 染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广。给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小。对于参数为k的几乎树,给出了多项式时间精确算法。也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数。
|
| 关 键 词： | 算法 染色多路割 固定参数可解 参数为k的几乎树 |
| 收稿时间： | 3/8/2009 12:00:00 AM |
| 修稿时间： | 2009/6/21 0:00:00 |
Colored Multiway Cuts in Almost Trees with Parameter k |
| |
| LI Shu-guang,XIN Xiao.Colored Multiway Cuts in Almost Trees with Parameter k[J].Computer Science,2010,37(2):246-249. |
| |
| Authors: | LI Shu-guang XIN Xiao |
| |
| Affiliation: | College of Computer Science and Technology/a>;Shandong Institute of Business and Technology/a>;Yantai 264005/a>;China;College of Foreign Studies/a>;China |
| |
| Abstract: | The colored multiway cut problem generalizes the traditional multiway cut problem.It is motivated by data partitioning in Peer-to-Peer networks.Given a graph G with color dependent edge weights and a partial coloration on some distinguished vertices,the colored multiway cut problem is to extend the partial coloration such that all the vertices are colored and the total weight of edges that have different colored endpoints is minimized.A polynomial time exact algorithm was presented for almost trees with par... |
| |
| Keywords: | Algorithms Colored multiway cuts Fixed-parameter tractable Almost trees with parameter k |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
