加權(quán)邊支配集問(wèn)題的參數(shù)算法研究.pdf

1、邊支配集（Edge Dominating Set）問(wèn)題是一類著名的NP難問(wèn)題，在很多領(lǐng)域都有重要應(yīng)用。在參數(shù)復(fù)雜性領(lǐng)域中，人們已對(duì)邊支配集和加權(quán)邊支配集問(wèn)題的參數(shù)算法作了大量研究。本文主要從參數(shù)復(fù)雜性角度出發(fā)，對(duì)加權(quán)邊支配集的兩個(gè)參數(shù)問(wèn)題：最小加權(quán)k-邊支配集問(wèn)題和加權(quán)邊支配集固定參數(shù)枚舉問(wèn)題展開(kāi)研究。 本文首先介紹了邊支配集問(wèn)題的研究現(xiàn)狀，并闡述了固定參數(shù)枚舉算法的基本概念及其具體應(yīng)用。 在邊支配集問(wèn)題的參數(shù)算法研究中

2、，分支搜索技術(shù)是解決該問(wèn)題的重要技術(shù)。本文對(duì)分支搜索技術(shù)的應(yīng)用進(jìn)行簡(jiǎn)要介紹，提出了最小加權(quán)k-邊支配集問(wèn)題的定義，并通過(guò)對(duì)問(wèn)題結(jié)構(gòu)的深入分析，結(jié)合匹配的性質(zhì)，獲得了一個(gè)算法運(yùn)行時(shí)間為O（42kk3+42kn2）的確定性參數(shù)算法。 在加權(quán)邊支配集問(wèn)題的固定參數(shù)枚舉算法研究中，本文主要采用枚舉擴(kuò)展的方法，將分支搜索技術(shù)和動(dòng)態(tài)規(guī)劃技術(shù)結(jié)合起來(lái)，提出了時(shí)間復(fù)雜度為O（5.62kk4z2+42knk3z）的有效枚舉算法對(duì)給定圖中前z個(gè)權(quán)值