反馈集问题的研究进展

摘要：

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

关键词：反馈顶点集、反馈边集、近似算法、精确算法、参数算法

所属期刊栏目：38

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金60773111;国家教育部创新团队资助计划IRT0661

在线出版日期：2011-04-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：40-47