覆蓋問題的參數算法研究.pdf

1、覆蓋問題是計算幾何和組合優(yōu)化領域中的一類重要的難解問題,對此類問題的研究不但具有重大的理論意義,而且在生物計算、電路設計、網絡選址、工藝流程分析等應用領域具有許多重要的實際意義。人們從實際應用中抽象出了許多的覆蓋問題,如頂點覆蓋問題、樹覆蓋問題、超平面覆蓋問題、集合覆蓋問題等。本文主要對超平面覆蓋問題和基于保證值的完美匹配圖中頂點覆蓋問題進行了深入的研究。
　　 對于超平面覆蓋問題,本文首先通過深入分析直線覆蓋問題(超平面覆蓋問

2、題的一個特例)的結構特征,提出了一個時間復雜度為O*((0.736κ)κ)的確定性的參數算法,較大地改進了以前最好的時間復雜度為O*((κ/2.2)2κ)的算法。更一般地,我們還提出了關于超平面覆蓋問題的確定性的參數算法,其時間復雜度為O*((dκ)!/((d!)κκ!)),較之前的時間復雜度為O*(κd(κ+1))的算法亦有較大改進。
　　 對于完美匹配圖中基于保證值的項點覆蓋問題,已有相關文獻提出了一個時間復雜度為O*(15

3、κ)的固定參數算法。本文對此算法作了進一步的改進,其整體思路是首先采用迭代壓縮技術將原問題轉化為求一個特殊的具有完美匹配的K(o)nig圖上的最小頂點覆蓋問題,然后將后者進一步轉化為參數化2-ASLASAT問題的一個變種問題(KPM-2-AASAT問題),最后,通過深入分析問題的結構特征,我們采用分枝搜索技術和隱含參數技術求解KPM-2-AASAT問題。整個算法的時間復雜度為O*(9κ),較之前最好結果有較大改進。
　　 本文最