反馈集问题的研究进展反馈集问题的研究进展.pdf

反馈集问题的研究进展 王建新江国红李文军陈建二 (中南大学信息科学与工程学院 沙410083) 搐要反馈集问题是经典的NP难问题，在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应 用。按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部有哪些信誉好的足球投注网站等 技术设计了一系列关于FVS和FAS问题的近似算法，并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确 算法。随着参数计算理论的发展，近年来参教化反馈集问题引起了人们的重视，并取得了很大突破。目前已经证明了 无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支有哪些信誉好的足球投注网站、迭代压缩等技术，对 无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用，人们开展了对具有特殊性质的图上FVS问题的研 究，提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法。然后 具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状，介绍了FAS问题 的研究成果。基于对反馈集问题研究现状的分析。提出了今后FVS问题研究中值得关注的几个方面。 关键词反馈顶点集．反馈边集，近似算法。精确算法，参数算法 中图法分类号TP301．6文献标识码A for Set FeedbackProblems：A Algorithms Survey WANG Li CHEN JiarrxinJiangGuo-hongWen-jun Jian-er ofInformationScienceand South 410083·China) (School Engineering。CentralUniversity，Changsha FeedbackVertex Feedback AbstractFeeclbackSet areclassicalNP include Set(FVS)and problems problems，which ofthese in ascircuit Arc are fields，such testing， Set(FAS)problems．Thereimportantapplicationsproblemsmany have different deadlock and many resolution，analyzingmanufacturingprocessescomputationalbiology．Peopledesigned basedonlinear andlocalsearch havefoundexact．solutions approximatealgorithms programming approaches，and by FeedbackSet havereceivedcon— Braneh-Pruneand