计算机科学 ›› 2010, Vol. 37 ›› Issue (2): 246-249.
• 人工智能 • 上一篇 下一篇
李曙光,辛晓
出版日期:
发布日期:
基金资助:
LI Shu-guang,XIN Xiao
Online:
Published:
摘要: 染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广。给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小。对于参数为k的几乎树,给出了多项式时间精确算法。也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数。
关键词: 算法,染色多路割,固定参数可解,参数为k的几乎树
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 parameter k. That is to say, the colored multiway cut problem is fixed-parameter tractable with respect to the parameter k, which is defined as the maximum, over all biconnected components C of the graph G, of the number of edges that must be removed from C to obtain a tree.
Key words: Algorithms,Colored multiway cuts,Fixed-parameter tractable,Almost trees with parameter k
李曙光,辛晓. 参数为k的几乎树中的染色多路割[J]. 计算机科学, 2010, 37(2): 246-249. https://doi.org/
LI Shu-guang,XIN Xiao. Colored Multiway Cuts in Almost Trees with Parameter k[J]. Computer Science, 2010, 37(2): 246-249. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2010/V37/I2/246
Cited