稀疏繼承圖難解問(wèn)題的核心化研究.pdf

1、稀疏繼承圖(Sparse-Hereditary Graphs)是一種重要的圖類(lèi)，包含了諸如d-degenerate圖，蔭度有界圖(Graphs with BondedAriboricity)，度有界圖(Bounded-Degree Graphs)，虧格有界圖(Graphswith Bounded Genus)、平面圖等一系列有重要理論及實(shí)際研究?jī)r(jià)值的圖類(lèi)。本文主要研究稀疏度小于3的稀疏繼承圖難解問(wèn)題的核心化。
　　 首先，本文通

2、過(guò)分析低度點(diǎn)與問(wèn)題解空間性質(zhì)的關(guān)系以及稀疏繼承圖的組合結(jié)構(gòu)性質(zhì)，對(duì)低度點(diǎn)制約的覆蓋問(wèn)題的核心化進(jìn)行了深入研究，證明了該類(lèi)問(wèn)題存在O(f(k)2)大小的核，其中f(k)是與問(wèn)題解相關(guān)的一個(gè)點(diǎn)規(guī)模函數(shù)。此外，通過(guò)得到的低度點(diǎn)制約覆蓋問(wèn)題核心化的結(jié)論，提出了設(shè)計(jì)稀疏繼承圖難解問(wèn)題核心化的基于低度點(diǎn)的核心化方法。以提出的低度點(diǎn)核心化方法為指導(dǎo)，本文對(duì)稀疏繼承圖連通點(diǎn)覆蓋、樹(shù)覆蓋、巡游覆蓋、邊支配集問(wèn)題進(jìn)行了深入研究。
　　 連通點(diǎn)覆蓋是

3、本文具體研究的第一個(gè)問(wèn)題。通過(guò)分析問(wèn)題解實(shí)例與低度點(diǎn)的關(guān)系，得到了若干有用的局部組合結(jié)構(gòu)性質(zhì)，基于得到的性質(zhì)設(shè)計(jì)了若干處理低度點(diǎn)的預(yù)處理規(guī)則，并得到稀疏繼承圖連通點(diǎn)覆蓋問(wèn)題大小為(6-α)k/(3-α)的核，其中1<α<3為稀疏繼承圖的稀疏度，這是該問(wèn)題的首個(gè)核心化結(jié)果。此外，本文通過(guò)研究虧格有界圖的結(jié)構(gòu)性質(zhì)，得到了虧格有界圖連通點(diǎn)覆蓋問(wèn)題大小為4(k+g)的核，特別地，當(dāng)g=0時(shí)，得到平面圖連通點(diǎn)覆蓋問(wèn)題大小為4k的核，改進(jìn)了目前最好

4、的結(jié)果14k。
　　 針對(duì)樹(shù)覆蓋，巡游覆蓋問(wèn)題，通過(guò)分析低度點(diǎn)與解空間的關(guān)系，設(shè)計(jì)了兩條預(yù)處理規(guī)則。基于得到的預(yù)處理規(guī)則將稀疏繼承圖樹(shù)覆蓋與巡游覆蓋問(wèn)題轉(zhuǎn)化為低度點(diǎn)制約的覆蓋問(wèn)題，并得到稀疏繼承圖樹(shù)覆蓋和巡游覆蓋問(wèn)題大小為O(k3)的核，這是該問(wèn)題的首個(gè)核心化結(jié)果。此外，研究了虧格有界圖樹(shù)覆蓋和巡游覆蓋問(wèn)題的核心化，得到這兩個(gè)問(wèn)題大小為3k2的核，是該問(wèn)題首個(gè)核心化結(jié)果。
　　 針對(duì)邊支配集問(wèn)題，通過(guò)分析低度點(diǎn)與解空間的

5、關(guān)系，設(shè)計(jì)了三條預(yù)處理規(guī)則，得到了稀疏繼承圖邊支配集問(wèn)題大小為O(k2)的核，這是該問(wèn)題的首個(gè)核心化結(jié)果。此外對(duì)虧格有界圖邊支配集問(wèn)題的核心化進(jìn)行了研究，得到該問(wèn)題大小為12k+10g的核，特別地，當(dāng)g=0時(shí)，得到平面圖邊支配集問(wèn)題大小為12k的核，改進(jìn)了目前最好的結(jié)果28k。
　　 本文進(jìn)一步推廣了低度點(diǎn)核心化方法的思想。研究了平面圖點(diǎn)不相交三角形包裝問(wèn)題的核心化，通過(guò)分析問(wèn)題的組合結(jié)構(gòu)性質(zhì)與“偽”低度點(diǎn)的關(guān)系，設(shè)計(jì)了若干高效