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

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

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