An efficient algorithm for constructing Hamiltonian paths in meshes

Shao Dong Chen, Hong Shen, Rodney Topor

Research output: Contribution to journalArticlepeer-review

41 Citations (Scopus)

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 languageEnglish
Pages (from-to)1293-1305
Number of pages13
JournalParallel Computing
Volume28
Issue number9
DOIs
Publication statusPublished - Sept 2002
Externally publishedYes

Keywords

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

Fingerprint

Dive into the research topics of 'An efficient algorithm for constructing Hamiltonian paths in meshes'. Together they form a unique fingerprint.

Cite this