TY - GEN

T1 - Efficient algorithms for the hamiltonian problem on distance-hereditary graphs

AU - Hsieh, Sun-Yuan

AU - Ho, Chin Wen

AU - Hsu, Tsan Sheng

AU - Ko, Ming Tat

PY - 2002/1/1

Y1 - 2002/1/1

N2 - In this paper, we first present an O(|V | + |E|)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G = (V,E). This algorithm is faster than the previous best result which takes O(|V|2) time. Let Td(|V|, |E|) and Pd(|V|, |E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph on a PRAM model Md.We also show that this problem can be solved in O(Td(|V|,|E|) + log |V|) time using O(Pd(|V|, |E|) + (|V | + |E|)/ log |V |) processors on Md. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log |V |) time using O((|V | + |E|)/ log |V |) processors on an EREW PRAM.

AB - In this paper, we first present an O(|V | + |E|)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G = (V,E). This algorithm is faster than the previous best result which takes O(|V|2) time. Let Td(|V|, |E|) and Pd(|V|, |E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph on a PRAM model Md.We also show that this problem can be solved in O(Td(|V|,|E|) + log |V|) time using O(Pd(|V|, |E|) + (|V | + |E|)/ log |V |) processors on Md. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log |V |) time using O((|V | + |E|)/ log |V |) processors on an EREW PRAM.

UR - http://www.scopus.com/inward/record.url?scp=84949783494&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949783494&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84949783494

SN - 354043996X

SN - 9783540439967

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 77

EP - 86

BT - Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings

A2 - Ibarra, Oscar H.

A2 - Zhang, Louxin

PB - Springer Verlag

T2 - 8th Annual International Conference on Computing and Combinatorics, COCOON 2002

Y2 - 15 August 2002 through 17 August 2002

ER -