最大內部點生成樹問題的算法及復雜性.pdf

1、本文重點研究了路徑覆蓋問題和內部頂點最多的生成樹問題的近似算法。本文的主要貢獻如下。
　　1、路徑覆蓋問題的近似算法及其復雜性的研究
　　給定一個無向簡單圖，路徑覆蓋問題要找的是一些沒有公共頂點的路徑，使得這些路徑能夠覆蓋圖的所有頂點并且它們的邊的總條數最多。一個圖的路徑覆蓋問題的最優(yōu)解是一條哈密頓路徑當且僅當該圖存在一條哈密頓路徑，因此，路徑覆蓋問題是哈密頓路徑問題的一般化。本文給出了路徑覆蓋問題的最優(yōu)解值的一個新的上界，

2、同時設計了求解路徑覆蓋問題的一個近似算法，利用所給出的上界，本文證明了該近似算法所得到的路徑的總的邊數至少是最優(yōu)解值的7/10倍。最后，我們證明了路徑覆蓋問題是APX-hard的，也就是說，如果P≠NP，那么，路徑覆蓋問題不存在多項式時間近似方案。
　　2、內部頂點最多的生成樹問題的近似算法及其復雜性研究
　　給定一個無向簡單圖，內部頂點最多的生成樹問題要找的是一棵內部頂點數目最多的生成樹。該問題同樣是哈密頓路徑問題的一般化

3、，因為，一個圖內部頂點最多的生成樹問題的最優(yōu)解是該圖的一條哈密頓路徑當且僅當該圖有一條哈密頓路徑。受路徑覆蓋問題研究的啟發(fā)，我們證明了一個圖的生成樹的內部頂點的數目不超過該圖的路徑覆蓋問題的最優(yōu)解值，又由于一個圖的路徑覆蓋問題的最優(yōu)解值不超過該圖的一個最大的圈-路徑覆蓋的邊的總條數，所以，一個圖的生成樹的內部頂點的數目不超過該圖的一個最大的圈-路徑覆蓋的邊的總條數。借助這個發(fā)現(xiàn)，我們利用圖的一個最大的圈-路徑覆蓋，首先設計了圖的內部頂點

4、最多的生成樹問題的近似性能比是1.5的多項式時間算法，該算法的性能已經是目前世界上最好的了。然后，我們又進一步將該算法的近似性能比改進到4/3。最后，我們證明，內部頂點最多的生成樹問題也是APX-hard的。
　　本文的進一步工作主要包括:
　　1、隨機近似技術目前是比較熱門的算法設計和分析的技術，通過實驗我們發(fā)現(xiàn)，很多情況下我們所得到的路徑覆蓋問題的解值十分接近最優(yōu)解值，我們猜想，是否存在一個隨機近似算法，使得該問題的平均

5、近似性能十分接近1。目前該問題還沒有一個隨機近似算法，所以，該方向應該是一個比較好的研究點。
　　2、對內部頂點最多的生成樹問題的近似算法的進一步研究主要有如下兩方面。
　　第一，我們可以接著本文的研究思路，進一步改進該算法的近似性能比。我們發(fā)現(xiàn)，該問題的障礙是圈-路徑覆蓋問題中的長度是4的路徑分支和長度是4的圈分支。要想改進近似性能比是(4/3)的算法，我們需要分別給出長度是4的路徑分支和圈分支所貢獻的內部頂點的數目的上界

6、。一旦這個上界有了，我們就很容易找到一個更好的近似算法了。
　　第二，我們可以利用局部搜索技術來改進算法的性能。局部搜索技術是目前比較熱門的算法設計和分析技術。陳建二等人已經利用局部搜索技術給出了一個內部頂點最多的生成樹問題的近似性能比是1.5的算法。我們猜想，把本文的算法和局部搜索技術相結合，也許會得到一個更好的算法。
　　3、路徑覆蓋問題和內部頂點最多的生成樹問題的不可近似性還是有很大的研究空間的，我們僅僅證明了這兩個問