## Abstract

This paper presents an efficient linear-time sequential algorithm for constructing Hamiltonian paths between two given vertices in meshes with horizontal size m and vertical size n. The algorithm first partitions the given mesh into a number of submeshes in constant steps, and then constructs a Hamiltonian cycle or path in each submesh and combines them together to become a complete Hamiltonian path in mn steps. Our algorithm has improved the previous algorithm by reducing the number of partition steps from O(m + n) to only a constant. Moreover, we show that our algorithm can be optimally parallelized to obtain a constant-time parallel algorithm on the weakest parallel machine without need of inter-processor communication, while this cannot be achieved for the previous algorithm.

Original language | English |
---|---|

Pages (from-to) | 1293-1305 |

Number of pages | 13 |

Journal | Parallel Computing |

Volume | 28 |

Issue number | 9 |

DOIs | |

Publication status | Published - Sept 2002 |

Externally published | Yes |

## Keywords

- Hamiltonian paths
- Meshes
- Performance evaluation
- Sequential and parallel algorithms