三個(gè)圖修改問(wèn)題的固定參數(shù)可解算法研究.pdf

1、本文針對(duì)三個(gè)NP-hard圖修改問(wèn)題設(shè)計(jì)固定參數(shù)可解算法。
　　 第一個(gè)問(wèn)題是如何從一個(gè)簡(jiǎn)單的無(wú)向圖中刪除最少的結(jié)點(diǎn)，使得剩余的圖中所有頂點(diǎn)的度都不大于3。在前人所給的時(shí)間復(fù)雜度為(0)*(3.24k)的固定參數(shù)算法中，先刪除度大于3的結(jié)點(diǎn)，然后處理兩個(gè)直接相連的度都為3的結(jié)點(diǎn)，考慮到這兩個(gè)結(jié)點(diǎn)的鄰居，這種情況會(huì)分出很多種子情況，其中它們的四個(gè)鄰居都為1的那種情況最為復(fù)雜，最后處理度為3的結(jié)點(diǎn)。本文針對(duì)該算法中最復(fù)雜的情況，通過(guò)

2、考慮這兩個(gè)結(jié)點(diǎn)的鄰居的鄰居來(lái)進(jìn)行細(xì)分，且對(duì)細(xì)分出的每一種情況進(jìn)行單獨(dú)處理:根據(jù)分析刪除最少的結(jié)點(diǎn)使得該情況滿(mǎn)足條件，最終把時(shí)間復(fù)雜度降到了(0)*(3.1k)。
　　 第二個(gè)問(wèn)題是如何從給定的有向圖中刪除最少的結(jié)點(diǎn)，使得剩余的圖中的每個(gè)結(jié)點(diǎn)的出度和入度都小于2。本文采用深度受限搜索樹(shù)技術(shù)設(shè)計(jì)了固定參數(shù)可解算法。該算法首先刪除出度和入度都大于3的結(jié)點(diǎn)，然后分析余下的圖，通過(guò)出度和入度的值來(lái)分情況處理，由于出度入度的值最大就為3，所

3、以總共有七種情況。并且對(duì)每種情況都給出相應(yīng)的處理:刪除掉最少的結(jié)點(diǎn)使得該情況出度和入度都符合小于等于1的要求。該算法的時(shí)間復(fù)雜度為(0)*(3k)。
　　 第三個(gè)問(wèn)題是如何從給定的無(wú)向圖中刪除最少邊后，剩余的圖中的每條邊的兩個(gè)端點(diǎn)的度至少有一個(gè)小于2。本文用深度受限搜索樹(shù)技術(shù)設(shè)計(jì)了固定參數(shù)可解算法。先對(duì)無(wú)向圖進(jìn)行預(yù)處理，首先把度大于2的結(jié)點(diǎn)全部標(biāo)記為黑點(diǎn)，然后再把兩端都是黑點(diǎn)的邊標(biāo)記為黑邊，接著處理標(biāo)記后圖中的黑邊:第一步處理三