Multicut问题参数算法的改进

• 作者: 刘运龙 王建新 陈建二
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: Muliticut Node Multicut 集合划分 极大恰当划分
• 年，卷（期）: 2010,（7）
• 页码范围: 1515-1523
• 分类号: TP301
• 字数: 11053字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03625

摘要

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*(「√2l」2l4k)的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*(2klkk4k3)的最好算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	刘运龙	中南大学信息科学与工程学院	5	10	2.0	2.0