反馈顶点集(Feedback Vertex Set,简称FVS)问题是经典的NP难问题,在电路测试、操作系统解死锁、网络设计、分析工艺流程、生物计算等领域都有重要应用。人们提出了一系列解决FVS问题算法技术,包括近似算法、精确算法和随机算法等。随着参数计算理论的发展,近年来参数化FVS问题引起了人们的重视,并对此问题的研究取得了很大突破。目前已经证明了无向图和有向图中FVS问题都是固定参数可解的(fixed-parameterized tractable,简称FPT)。本文研究了带权无向图中FVS问题的固定参数枚举技术,提出了一种有效的基于分支搜索技术的固定参数枚举算法。首先求出给定图G的一个含k个顶点的FVS F;然后基于F对图G进行结构划分,对各结构划分利用分支搜索技术求得满足一定条件的图结构,从而将FVS问题转化为反馈边集(Feedback Edge Set,简称FES)问题;最后通过枚举z个权值最大森林来枚举z个权值最小的FES,进而枚举出z个权值最小的含k个顶点的FVS。整个算法时间复杂度为O(5~kkn~2+(5~k+3~kz)n~2 logn)。本文还研究了竞赛图(Tournaments)的参数化带权FVS问题,即在竞赛图中找一个权值最小的含顶点数不超过k的FVS。首先,利用求解竞赛图中不带权FVS问题的FPT算法求出一个含k个点的FVS F;然后对F进行划分,并对每种划分,将问题转化为相同子序列(Common Subsequence)问题而求得基于此划分的权值最小的FVS;基于所有划分的FVS中权值最小的一个FVS即为问题的解。本文分别用分支搜索和动态规划两种技术求解相同子序列问题,从而对参数化带权FVS问题提出了时间复杂度分别为O(3~kn)和O(2~kn~2(logn+k))的算法。本文最后对FVS问题的研究工作进行了总结,并阐述了对该问题的进一步研究工作。