反馈集问题的研究进展

• 作者: 李文军 江国红 王建新 陈建二
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 反馈顶点集 反馈边集 近似算法 精确算法 参数算法
• 年，卷（期）: 2011,（1）
• 页码范围: 40-47
• 分类号: TP301.6
• 字数: 10212字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2011.01.008

摘要

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题.人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝-剪枝策略和加权分治技术提出了FVS问题的精确算法.随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破.目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT).利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法.针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法.现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法.进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果.基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面.

作者信息

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