参数为k的几乎树中的染色多路割

摘要：

染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广.给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小.对于参数为k的几乎树,给出了多项式时间精确算法.也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数.

关键词：算法、染色多路割、固定参数可解、参数为k的几乎树

所属期刊栏目：37

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60673153,60970105;山东省信息产业发展专项资金项目2008X00039

在线出版日期：2010-04-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：246-249