带权无向图中反馈顶点集的固定参数枚举算法  

Fixed Parameter Enumeration Algorithm for Feedback Vertex Set in Weighted Undirected Graphs

作　　者：王建新[1] 江国红[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机学报》2010年第7期1140-1152,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(60773111;60873265);国家"九七三"重点基础研究发展规划项目基金前期研究专项(2008CB317107);国家教育部创新团队资助计划(IRT0661)资助~~

摘　　要：反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).Feedback vertex set （FVS） problem is a classical NP-complete problem. There are important applications of the problem in many areas. Many studies have been done on the FVS problem, but there is no effective algorithm to enumerate the FVS in weighted undirected graphs. In this paper, a fixed-parameter enumeration algorithm based on the branch-and-search technique is given by analyzing the structure of the FVS problem in weighted undirected graphs. In the algorithm, the feedback vertex set problem is transformed to feedback edge set （FES） problem and the z minimum-weight FES of size k are enumerated by enumerating z maximum- weight forests, then the z minimum-weight FVS of size k can be found. The fixed-parameter enumeration algorithm for FVS runs in time O（S^kn^2 （logn＋k）＋3^kz（n^2logn＋z））.

关 键 词：反馈顶点集 无向图 带权 参数 固定参数枚举 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]