參數(shù)化反饋?lái)旤c(diǎn)集問(wèn)題的研究.pdf

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

2、ized tractable，簡(jiǎn)稱(chēng)FPT）。 本文研究了帶權(quán)無(wú)向圖中FVS問(wèn)題的固定參數(shù)枚舉技術(shù)，提出了一種有效的基于分支搜索技術(shù)的固定參數(shù)枚舉算法。首先求出給定圖G的一個(gè)含k個(gè)頂點(diǎn)的FVS F；然后基于F對(duì)圖G進(jìn)行結(jié)構(gòu)劃分，對(duì)各結(jié)構(gòu)劃分利用分支搜索技術(shù)求得滿足一定條件的圖結(jié)構(gòu)，從而將FVS問(wèn)題轉(zhuǎn)化為反饋邊集（Feedback Edge Set，簡(jiǎn)稱(chēng)FES）問(wèn)題；最后通過(guò)枚舉z個(gè)權(quán)值最大森林來(lái)枚舉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）。 本文還研究了競(jìng)賽圖（Toumaments）的參數(shù)化帶權(quán)FVS問(wèn)題，即在競(jìng)賽圖中找一個(gè)權(quán)值最小的含頂點(diǎn)數(shù)不超過(guò)k的FVS。首先，利用求解競(jìng)賽圖中不帶權(quán)FVS問(wèn)題的FPT算法求出一個(gè)含k個(gè)點(diǎn)的FVS F；然后對(duì)F進(jìn)行劃分，并對(duì)每種劃分，將問(wèn)題轉(zhuǎn)化為相同子序列（Common Subsequence）問(wèn)題而求得基于此劃分的權(quán)值最小的