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