@inproceedings{b65d0f527f46477eaa95a0bca505a41b,
title = "Efficient algorithms for the hamiltonian problem on distance-hereditary graphs",
abstract = "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.",
author = "Hsieh, {Sun Yuan} and Ho, {Chin Wen} and Hsu, {Tsan Sheng} and Ko, {Ming Tat}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 8th Annual International Conference on Computing and Combinatorics, COCOON 2002 ; Conference date: 15-08-2002 Through 17-08-2002",
year = "2002",
doi = "10.1007/3-540-45655-4_10",
language = "???core.languages.en_GB???",
isbn = "354043996X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "77--86",
editor = "Ibarra, {Oscar H.} and Louxin Zhang",
booktitle = "Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings",
}