最小邊排名問題的若干算法研究
論文摘要: 最小邊(點(diǎn))排名問題是指如何使用最少的正整數(shù)給邊(點(diǎn))賦權(quán)值使得連接兩個具有相同（略）點(diǎn))的任何一條路徑上總存在一個權(quán)值大于i的邊(點(diǎn)).最小邊排名問題在組裝產(chǎn)品過程的并行組裝調(diào)度方面有重要的應(yīng)用.最小點(diǎn)排名問題則在正定矩陣的并行（略）ky分解、并行查詢處理以及程序驗證方面都有重要的應(yīng)用.這兩個問題在一般圖上已經(jīng)被證明是NP-hard的.在很多特殊圖上(例如樹、排列圖和區(qū)間圖等（略）名問題卻存在多項式時間的求解算法.與最小點(diǎn)排名問題相比,最小邊排名問題的結(jié)論則相對較少,目前已知的是樹、2-連通的外平面圖和完全k-部圖上的最小邊排名問題具有多項式求解算法. 本文主要研究了特殊圖上的最小邊排名問題.具體地本文研究了樹寬和度數(shù)均有界的圖上的最�。裕┎⒔o出了一個多項式時間求解算法.另外本文也從參數(shù)復(fù)雜性的角度考察了參數(shù)化的最小邊排名問題的復(fù)雜性,給出了一個固定參數(shù)可解算法,從而說明參數(shù)化的最小邊排（略）參數(shù)可解的. 針對樹寬和度數(shù)均有界的圖上的最小邊排名問題,本文將其轉(zhuǎn)化為對應(yīng)線圖上的最小點(diǎn)排名問題并證明此時對應(yīng)線圖的樹寬也是有界的,從而可以利用已有的樹寬有界...
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頁
Abstract 第5-6頁
第1章 引言 第8-12頁
·課題的研究背景和意義 第9-10頁
·課題的研究內(nèi)容 第10-11頁
·論文組織 第11-12頁
第2章 相關(guān)研究工作 第12-25頁
·本文用到的一些術(shù)語 第12-15頁
·圖論的基本概念 第12-14頁
·參數(shù)復(fù)雜性理論簡介 第14-15頁
·點(diǎn)排名問題的研究現(xiàn)狀 第15-19頁
·邊排名問題的研究現(xiàn)狀 第19-24頁
·- 連通的外平面圖上的邊排名 第20-22頁
·樹上的邊排名 第22-24頁
·本章小結(jié) 第24-25頁
第3章 樹寬和度數(shù)均有界的圖上的最小邊排名問題 第25-40頁
·將最小邊排名問題轉(zhuǎn)化為最小點(diǎn)排名問題 第25-27頁
·求解樹寬有界的圖上的最小點(diǎn)排名問題 第27-38頁
·求解樹寬有界圖的點(diǎn)排名判定問題 第27-36頁
·樹寬有界圖的最小點(diǎn)排名的一個上界 第36-38頁
·求樹寬和度數(shù)均有界的圖上的最小邊排名問題 第38-39頁
·本章小結(jié) 第39-40頁
第4章 最小邊排名問題的一個FPT算法 第40-45頁
·求解最小邊排名問題的一個FPT算法 第40-44頁
·本章小結(jié) 第44-45頁
第5章 結(jié)束語 第45-48頁
·研究工作總結(jié) 第45-46頁
·進(jìn)一步研究工作 第46-48頁
參考文獻(xiàn) 第48-53頁
致謝 第53-54頁
研究成果 第54頁
【最小邊排名問題的若干算法研究】相關(guān)文章：
最小邊排名問題的若干算法研究寫作提綱12-05
新媒體藝術(shù)的若干問題研究11-17
淺析成人高等教育若干心理問題的研究01-13
地鐵結(jié)構(gòu)抗震研究中的若干問題論文03-04
關(guān)于電力網(wǎng)諧波若干問題的研究論文11-19
林權(quán)流轉(zhuǎn)過程中的若干問題研究提綱12-04
- 相關(guān)推薦