最小邊排名問(wèn)題的若干算法研究

論文摘要: 最小邊(點(diǎn))排名問(wèn)題是指如何使用最少的正整數給邊(點(diǎn))賦權值使得連接兩個(gè)具有相同（略）點(diǎn))的任何一條路徑上總存在一個(gè)權值大于i的邊(點(diǎn)).最小邊排名問(wèn)題在組裝產(chǎn)品過(guò)程的并行組裝調度方面有重要的應用.最小點(diǎn)排名問(wèn)題則在正定矩陣的并行（略）ky分解、并行查詢(xún)處理以及程序驗證方面都有重要的應用.這兩個(gè)問(wèn)題在一般圖上已經(jīng)被證明是NP-hard的.在很多特殊圖上(例如樹(shù)、排列圖和區間圖等（略）名問(wèn)題卻存在多項式時(shí)間的求解算法.與最小點(diǎn)排名問(wèn)題相比,最小邊排名問(wèn)題的結論則相對較少,目前已知的是樹(shù)、2-連通的外平面圖和完全k-部圖上的最小邊排名問(wèn)題具有多項式求解算法. 本文主要研究了特殊圖上的最小邊排名問(wèn)題.具體地本文研究了樹(shù)寬和度數均有界的圖上的最�。�略）并給出了一個(gè)多項式時(shí)間求解算法.另外本文也從參數復雜性的角度考察了參數化的最小邊排名問(wèn)題的復雜性,給出了一個(gè)固定參數可解算法,從而說(shuō)明參數化的最小邊排（略）參數可解的. 針對樹(shù)寬和度數均有界的圖上的最小邊排名問(wèn)題,本文將其轉化為對應線(xiàn)圖上的最小點(diǎn)排名問(wèn)題并證明此時(shí)對應線(xiàn)圖的樹(shù)寬也是有界的,從而可以利用已有的樹(shù)寬有界...
The minimum edge （omitted）ankin（omitted）is to find a weight assignment of the edges (vertices) of the input graph with leas（omitted）f integers such that every path connecting two edges (vertices) with the same weight i contains an intermediat（omitted）rtex) with weight greater than i. The minimum edge ranking problem has application in scheduling of parallel assembly of a product from its components while（omitted）um vertex ranking problem plays an important role in computing Cholesky factorization...
目錄:摘要 第4-5頁(yè)
Abstract 第5-6頁(yè)
第1章 引言 第8-12頁(yè)
　　·課題的研究背景和意義 第9-10頁(yè)
　　·課題的研究?jì)热?第10-11頁(yè)
　　·論文組織 第11-12頁(yè)
第2章 相關(guān)研究工作 第12-25頁(yè)
　　·本文用到的一些術(shù)語(yǔ) 第12-15頁(yè)
　　　　·圖論的基本概念 第12-14頁(yè)
　　　　·參數復雜性理論簡(jiǎn)介 第14-15頁(yè)
　　·點(diǎn)排名問(wèn)題的研究現狀 第15-19頁(yè)
　　·邊排名問(wèn)題的研究現狀 第19-24頁(yè)
　　　　·- 連通的外平面圖上的邊排名 第20-22頁(yè)
　　　　·樹(shù)上的邊排名 第22-24頁(yè)
　　·本章小結 第24-25頁(yè)
第3章 樹(shù)寬和度數均有界的圖上的最小邊排名問(wèn)題 第25-40頁(yè)
　　·將最小邊排名問(wèn)題轉化為最小點(diǎn)排名問(wèn)題 第25-27頁(yè)
　　·求解樹(shù)寬有界的圖上的最小點(diǎn)排名問(wèn)題 第27-38頁(yè)
　　　　·求解樹(shù)寬有界圖的點(diǎn)排名判定問(wèn)題 第27-36頁(yè)
　　　　·樹(shù)寬有界圖的最小點(diǎn)排名的一個(gè)上界 第36-38頁(yè)
　　·求樹(shù)寬和度數均有界的圖上的最小邊排名問(wèn)題 第38-39頁(yè)
　　·本章小結 第39-40頁(yè)
第4章 最小邊排名問(wèn)題的一個(gè)FPT算法 第40-45頁(yè)
　　·求解最小邊排名問(wèn)題的一個(gè)FPT算法 第40-44頁(yè)
　　·本章小結 第44-45頁(yè)
第5章 結束語(yǔ) 第45-48頁(yè)
　　·研究工作總結 第45-46頁(yè)
　　·進(jìn)一步研究工作 第46-48頁(yè)
參考文獻 第48-53頁(yè)
致謝 第53-54頁(yè)
研究成果 第54頁(yè)

【最小邊排名問(wèn)題的若干算法研究】相關(guān)文章：

最小邊排名問(wèn)題的若干算法研究寫(xiě)作提綱12-05

新媒體藝術(shù)的若干問(wèn)題研究11-17

淺析成人高等教育若干心理問(wèn)題的研究01-13

機器帶中斷的若干延誤問(wèn)題研究論文提綱11-18

地鐵結構抗震研究中的若干問(wèn)題論文03-04

關(guān)于電力網(wǎng)諧波若干問(wèn)題的研究論文11-19

淺析普通高校教學(xué)管理若干問(wèn)題的研究03-09

林權流轉過(guò)程中的若干問(wèn)題研究提綱12-04

淺析普通高校教學(xué)管理若干問(wèn)題的研究論文02-23