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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence