### 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|^{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 1 |

### All Science Journal Classification (ASJC) codes

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