最小邊排名問題的若干算法研究.pdf

1、最小邊(點)排名問題是指如何使用最少的正整數給邊(點)賦權值使得連接兩個具有相同權值i的邊(點)的任何一條路徑上總存在一個權值大于i的邊(點)。最小邊排名問題在組裝產品過程的并行組裝調度方面有重要的應用。最小點排名問題則在正定矩陣的并行Cholesky分解、并行查詢處理以及程序驗證方面都有重要的應用。這兩個問題在一般圖上已經被證明是NP-hard的。在很多特殊圖上(例如樹、排列圖和區(qū)間圖等)的最小點排名問題卻存在多項式時間的求解算法。與

2、最小點排名問題相比,最小邊排名問題的結論則相對較少,目前已知的是樹、2-連通的外平面圖和完全k-部圖上的最小邊排名問題具有多項式求解算法。
　　 本文主要研究了特殊圖上的最小邊排名問題。具體地本文研究了樹寬和度數均有界的圖上的最小邊排名問題,并給出了一個多項式時間求解算法。另外本文也從參數復雜性的角度考察了參數化的最小邊排名問題的復雜性,給出了一個固定參數可解算法,從而說明參數化的最小邊排名問題是固定參數可解的。
　　

3、針對樹寬和度數均有界的圖上的最小邊排名問題,本文將其轉化為對應線圖上的最小點排名問題并證明此時對應線圖的樹寬也是有界的,從而可以利用已有的樹寬有界的圖上的最小點排名問題的多項式時間求解算法,最終得到了原問題的一個多項式時間求解算法。
　　 針對參數化的最小邊排名問題,本文選擇所求邊排名的大小作為參數。通過證明若圖的最小邊排名有界那么圖的度數和直徑均有界,結合度數和直徑問題具有Moore上界,本文得到了參數化最小邊排名問題的一個核