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

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

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

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