The Hamiltonian problem on distance-hereditary graphs

Sun Yuan Hsieh, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n2) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.

Original languageEnglish
Pages (from-to)508-524
Number of pages17
JournalDiscrete Applied Mathematics
Issue number3
StatePublished - 1 Mar 2006


  • Distance-hereditary graphs
  • Parallel algorithms
  • PRAM
  • The Hamiltonian problem


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

Cite this