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

Research output: Contribution to journalArticle

6 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)662-685
Number of pages24
JournalJournal of Parallel and Distributed Computing
Volume64
Issue number5
DOIs
Publication statusPublished - 2004 May 1

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs'. Together they form a unique fingerprint.

  • Cite this