论文部分内容阅读
反馈顶点集（FVS）问题是一个经典的NP-完全问题，在很多领域有重要的应用．人们对该问题进行了大量的研究，但目前还没有有效的算法枚举带权无向图的反馈顶点集．文中通过对带权无向图中反馈顶点集问题的结构的深入分析，给出了一个有效的基于分支搜索技术的固定参数枚举算法．算法将反馈顶点集问题转化为反馈边集问题，通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集，从而得到z个权值最小的含k个顶点的反馈顶点集，算法时间复杂度为O（5^kn^2（logn＋k）十3^kz（n^2logn＋z））．