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

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

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