距離繼承圖上的最長路徑問題; The Longest Path Problem on Distance-hereditary Graphs

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/61085

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/61085

题名:	距離繼承圖上的最長路徑問題;The Longest Path Problem on Distance-hereditary Graphs
作者:	郭易祿;Guo,Yi-Lu
贡献者:	資訊工程學系
关键词:	最長路徑問題;距離繼承圖;多項式時間演算法;Longest path problem;Distance-hereditary graphs;Polynomial-time algorithms
日期:	2013-07-11
上传时间:	2013-08-22 12:11:32 (UTC+8)
出版者:	國立中央大學
摘要:	中文摘要在本論文中，我們於距離繼承圖中求解最長路徑問題。所謂的最長路徑問題即為於圖形中找出一條最長的簡單路徑問題，為漢彌爾頓路徑問題的一般化，故於一般圖形中求解難度為一NP-complete問題。所謂的距離繼承圖其性質為：對於圖上任意兩點，其間的的最短距離於任何原圖的誘導子圖中都相同。本篇論文利用距離繼承圖的特性，於O(n4)時間內求解距離繼承圖上的最長路徑問題。 Abstract. The longest path problem is to find a path of maximum length in a graph. As a generalization of Hamiltonian path problem, it is NP-complete on general graphs. A graph is called distance-hereditary if the distance of each pair of vertices in every connected induced subgraph containing them are the same. In this dissertation, we present an O(n4) time algorithm to solve the longest path problem on a distance-hereditary graph of n vertices.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	774	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing