The Hamiltonian problem on distance-hereditary graphs

In this paper, we first present an O(n+m)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)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)O(logn) time using O((n+m)/logn)O((n+m)/logn) processors on an EREW PRAM.