參數(shù)化反饋頂點(diǎn)集問題的研究.pdf

1、反饋頂點(diǎn)集（Feedback Vertex Set，簡稱FVS）問題是經(jīng)典的NP難問題，在電路測試、操作系統(tǒng)解死鎖、網(wǎng)絡(luò)設(shè)計(jì)、分析工藝流程、生物計(jì)算等領(lǐng)域都有重要應(yīng)用。 人們提出了一系列解決FVS問題算法技術(shù)，包括近似算法、精確算法和隨機(jī)算法等。隨著參數(shù)計(jì)算理論的發(fā)展，近年來參數(shù)化FVS問題引起了人們的重視，并對此問題的研究取得了很大突破。目前已經(jīng)證明了無向圖和有向圖中FVS問題都是固定參數(shù)可解的（fixed-parameter

2、ized tractable，簡稱FPT）。 本文研究了帶權(quán)無向圖中FVS問題的固定參數(shù)枚舉技術(shù)，提出了一種有效的基于分支搜索技術(shù)的固定參數(shù)枚舉算法。首先求出給定圖G的一個(gè)含k個(gè)頂點(diǎn)的FVS F；然后基于F對圖G進(jìn)行結(jié)構(gòu)劃分，對各結(jié)構(gòu)劃分利用分支搜索技術(shù)求得滿足一定條件的圖結(jié)構(gòu)，從而將FVS問題轉(zhuǎn)化為反饋邊集（Feedback Edge Set，簡稱FES）問題；最后通過枚舉z個(gè)權(quán)值最大森林來枚舉z個(gè)權(quán)值最小的FES，進(jìn)而枚舉出

3、z個(gè)權(quán)值最小的含k個(gè)頂點(diǎn)的FVS。整個(gè)算法時(shí)間復(fù)雜度為0（5kkn2+（5k+3kz）n2 logn）。 本文還研究了競賽圖（Toumaments）的參數(shù)化帶權(quán)FVS問題，即在競賽圖中找一個(gè)權(quán)值最小的含頂點(diǎn)數(shù)不超過k的FVS。首先，利用求解競賽圖中不帶權(quán)FVS問題的FPT算法求出一個(gè)含k個(gè)點(diǎn)的FVS F；然后對F進(jìn)行劃分，并對每種劃分，將問題轉(zhuǎn)化為相同子序列（Common Subsequence）問題而求得基于此劃分的權(quán)值最小的