Paper Info
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.
Year
DOI
Venue
2002
10.1007/3-540-45655-4_10
COCOON
Keywords
Field
DocType
processor complexity,pram model,hamiltonian problem,distance-hereditary graphs,decomposition tree form,erew pram,distance-hereditary graph,previous best result,time sequential algorithm,parallel time,efficient algorithms,decomposition tree
Discrete mathematics,Combinatorics,Tree (graph theory),Hamiltonian (quantum mechanics),Hamiltonian path,Steiner tree problem,Parallel algorithm,Algorithm,Cycle graph,Sequential algorithm,Time complexity,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-43996-X
7
0.46
References 
Authors
13
4
Name
Order
Citations
PageRank
Sun-Yuan Hsieh11715112.85
Chin-Wen Ho257339.27
Tsan-sheng Hsu3737101.00
Ming-Tat Ko41320103.71