An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

Sun Yuan Hsieh

doi:10.1016/j.jpdc.2004.03.014

An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

Sun Yuan Hsieh

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let T_d(|V|,|E|) and P_d(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M_d. We show that this problem can be solved in O(T_d(|V|,|E|)+log|V|) time using O(P_d(|V|,|E|)+(|V|+|E|)/log|V|) processors on M_d. 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. We also obtain a linear-time algorithm which is faster than the previous known O(|V|³) sequential algorithm.

Original language	English
Pages (from-to)	662-685
Number of pages	24
Journal	Journal of Parallel and Distributed Computing
Volume	64
Issue number	5
DOIs	https://doi.org/10.1016/j.jpdc.2004.03.014
Publication status	Published - 2004 May

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Access to Document

10.1016/j.jpdc.2004.03.014

Cite this

@article{0d73334cb0c146a39021d2ba3cd562a2,

title = "An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs",

abstract = "In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. 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 G=(V,E) on a PRAM model Md. We 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. We also obtain a linear-time algorithm which is faster than the previous known O(|V|3) sequential algorithm.",

author = "Hsieh, \{Sun Yuan\}",

year = "2004",

month = may,

doi = "10.1016/j.jpdc.2004.03.014",

language = "English",

volume = "64",

pages = "662--685",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

AU - Hsieh, Sun Yuan

PY - 2004/5

Y1 - 2004/5

N2 - In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. 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 G=(V,E) on a PRAM model Md. We 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. We also obtain a linear-time algorithm which is faster than the previous known O(|V|3) sequential algorithm.

AB - In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. 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 G=(V,E) on a PRAM model Md. We 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. We also obtain a linear-time algorithm which is faster than the previous known O(|V|3) sequential algorithm.

UR - https://www.scopus.com/pages/publications/4544307932

UR - https://www.scopus.com/pages/publications/4544307932#tab=citedBy

U2 - 10.1016/j.jpdc.2004.03.014

DO - 10.1016/j.jpdc.2004.03.014

M3 - Article

AN - SCOPUS:4544307932

SN - 0743-7315

VL - 64

SP - 662

EP - 685

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 5

ER -

An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this