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