The longest path problem on distance-hereditary graphs

Yi Lu Guo, Chin Wen Ho, Ming Tat Ko

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

2 Scopus citations


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.

Original languageEnglish
Title of host publicationAdvances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan
EditorsJain Lakhmi, Chang Ruay-Shiung, Peng Sheng-Lung
Number of pages9
StatePublished - 2013

Publication series

NameSmart Innovation, Systems and Technologies
ISSN (Print)2190-3018
ISSN (Electronic)2190-3026


  • Distance-hereditary graphs
  • Longest path problem
  • Polynomialtime algorithm


Dive into the research topics of 'The longest path problem on distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this