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

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/61085

Title:	距離繼承圖上的最長路徑問題;The Longest Path Problem on Distance-hereditary Graphs
Authors:	郭易祿;Guo,Yi-Lu
Contributors:	資訊工程學系
Keywords:	最長路徑問題;距離繼承圖;多項式時間演算法;Longest path problem;Distance-hereditary graphs;Polynomial-time algorithms
Date:	2013-07-11
Issue Date:	2013-08-22 12:11:32 (UTC+8)
Publisher:	國立中央大學
Abstract:	中文摘要在本論文中，我們於距離繼承圖中求解最長路徑問題。所謂的最長路徑問題即為於圖形中找出一條最長的簡單路徑問題，為漢彌爾頓路徑問題的一般化，故於一般圖形中求解難度為一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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	774	View/Open

社群 sharing