CAJ | 학술논문

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题.人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝-剪枝策略和加权分治技术提出了FVS问题的精确算法.随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破.目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT).利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法.针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法.现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法.进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果.基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面.
반궤집문제시경전적NP난문제,재전로측시、조작계통해사쇄、분석공예류정、생물계산등영역도유중요응용,안조반궤집중원소류형가분위반궤정점집(FVS)문제화반궤변집(FAS)문제.인문이용선성규화화국부수색등기술설계료일계렬관우FVS화FAS문제적근사산법,병기우분지-전지책략화가권분치기술제출료FVS문제적정학산법.수착삼수계산이론적발전,근년래삼수화반궤집문제인기료인문적중시,병취득료흔대돌파.목전이경증명료무향도화유향도중FVS문제화FAS문제도시고정삼수가해적(FPT).이용수분해、분지수색、질대압축등기술,대무향도FVS문제제출료일계렬FPT산법.침대모사특수적응용,인문개전료대구유특수성질적도상FVS문제적연구,제출료일사다항식시간가해적정학산법.현수선개소료재무향도중관우FVS문제적근사산법여정학산법,연후구체분석료FVS문제적삼수화산법.진일보천술료관우유향도화특수도상FVS문제적연구현상,개소료FAS문제적연구성과.기우대반궤집문제연구현상적분석,제출료금후FVS문제연구중치득관주적궤개방면.