反馈集问题的研究进展

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

一种求取环网方向保护断点集的实用算法

将保护断点集的求取问题转换为寻找有向图中反馈边集问题。通过对反馈边集特性的研究,提出一种快速寻找反馈边集的实用方法,并论证了该方法的理论依据,进而采用该方法启发式搜索电网中保护之间的主/后备配合的依赖关系集,可去除无效的搜索起点和重复的搜索回路,快速得到环网保护整定的断点集。该方法可在电网拓扑发生变化时,通过修改相关保护间的依赖关系,就可在原有搜索结果的基础上,快速得到新的断点集。最后通过算例证明了新方法的正确性。