10.3969/j.issn.1002-137X.2010.02.061
参数为k的几乎树中的染色多路割
染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广.给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小.对于参数为k的几乎树,给出了多项式时间精确算法.也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数.
算法、染色多路割、固定参数可解、参数为k的几乎树
37
TP301(计算技术、计算机技术)
国家自然科学基金60673153,60970105;山东省信息产业发展专项资金项目2008X00039
2010-04-19(万方平台首次上网日期,不代表论文的发表时间)
共4页
246-249