Abstract
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 language | English |
---|---|
Pages (from-to) | 508-524 |
Number of pages | 17 |
Journal | Discrete Applied Mathematics |
Volume | 154 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2006 Mar 1 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics