带权无向图中反馈顶点集的固定参数枚举算法

• 作者: 江国红 王建新 陈建二
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 反馈顶点集 无向图 带权 参数 固定参数枚举
• 年，卷（期）: 2010,（7）
• 页码范围: 1140-1152
• 分类号: TP301
• 字数: 16625字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.01140

摘要

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).

作者信息

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