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

• 作者: 李曙光 辛晓
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 算法 染色多路割 固定参数可解 参数为k的几乎树
• 年，卷（期）: 2010,（2）
• 所属期刊栏目: 人工智能
• 页码范围: 246-249
• 页数: 4页
• 分类号: TP301
• 字数: 5860字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2010.02.061

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	辛晓	山东工商学院外国语学院	3	11	1.0	3.0
2	李曙光	山东工商学院计算机科学与技术学院	4	2	1.0	1.0