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 distances of each pair of vertices in every connected induced subgraph containing them are the same. In this paper, we present an O(n4) time algorithm to solve the longest path problem on a distance-hereditary graph of n vertices.
|主出版物標題||Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan|
|編輯||Jain Lakhmi, Chang Ruay-Shiung, Peng Sheng-Lung|
|出版狀態||已出版 - 2013|
|名字||Smart Innovation, Systems and Technologies|