| DC 欄位 |
值 |
語言 |
| DC.contributor | 資訊工程學系 | zh_TW |
| DC.creator | 郭易祿 | zh_TW |
| DC.creator | Yi-Lu Guo | en_US |
| dc.date.accessioned | 2013-7-11T07:39:07Z | |
| dc.date.available | 2013-7-11T07:39:07Z | |
| dc.date.issued | 2013 | |
| dc.identifier.uri | http://ir.lib.ncu.edu.tw:444/thesis/view_etd.asp?URN=995202038 | |
| dc.contributor.department | 資訊工程學系 | zh_TW |
| DC.description | 國立中央大學 | zh_TW |
| DC.description | National Central University | en_US |
| dc.description.abstract | 中文摘要
在本論文中，我們於距離繼承圖中求解最長路徑問題。所謂的最長路徑問題即為於圖形中找出一條最長的簡單路徑問題，為漢彌爾頓路徑問題的一般化，故於一般圖形中求解難度為一NP-complete問題。所謂的距離繼承圖其性質為：對於圖上任意兩點，其間的的最短距離於任何原圖的誘導子圖中都相同。本篇論文利用距離繼承圖的特性，於O(n4)時間內求解距離繼承圖上的最長路徑問題。 | zh_TW |
| dc.description.abstract | 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. | en_US |
| DC.subject | 最長路徑問題 | zh_TW |
| DC.subject | 距離繼承圖 | zh_TW |
| DC.subject | 多項式時間演算法 | zh_TW |
| DC.subject | Longest path problem | en_US |
| DC.subject | Distance-hereditary graphs | en_US |
| DC.subject | Polynomial-time algorithms | en_US |
| DC.title | 距離繼承圖上的最長路徑問題 | zh_TW |
| dc.language.iso | zh-TW | zh-TW |
| DC.title | The Longest Path Problem on Distance-hereditary Graphs | en_US |
| DC.type | 博碩士論文 | zh_TW |
| DC.type | thesis | en_US |
| DC.publisher | National Central University | en_US |