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 language | English |
---|---|
Pages (from-to) | 662-685 |
Number of pages | 24 |
Journal | Journal of Parallel and Distributed Computing |
Volume | 64 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2004 May |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence