最小邊排名問題的若干算法研究寫作提綱

時間：2024-08-28 04:23:57 論文提綱我要投稿

最小邊排名問題的若干算法研究寫作提綱

論文摘要: 最小邊(點(diǎn))排名問題是指如何使用最少的正整數(shù)給邊(點(diǎn))賦權(quán)值使得連接兩個具有相同（略）點(diǎn))的任何一條路徑上總存在一個權(quán)值大于i的邊(點(diǎn)).最小邊排名問題在組裝產(chǎn)品過程的并行組裝調(diào)度方面有重要的應(yīng)用.最小點(diǎn)排名問題則在正定矩陣的并行（略）ky分解、并行查詢處理以及程序驗(yàn)證方面都有重要的應(yīng)用.這兩個問題在一般圖上已經(jīng)被證明是NP-hard的.在很多特殊圖上(例如樹、排列圖和區(qū)間圖等（略）名問題卻存在多項(xiàng)式時間的求解算法.與最小點(diǎn)排名問題相比,最小邊排名問題的結(jié)論則相對較少,目前已知的是樹、2-連通的外平面圖和完全k-部圖上的最小邊排名問題具有多項(xiàng)式求解算法. 本文主要研究了特殊圖上的最小邊排名問題.具體地本文研究了樹寬和度數(shù)均有界的圖上的最�。裕┎⒔o出了一個多項(xiàng)式時間求解算法.另外本文也從參數(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頁