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

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

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

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