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

摘要

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