An efficient algorithm for constructing Hamiltonian paths in meshes

✍ Scribed by Shao Dong Chen; Hong Shen; Rodney Topor

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 169 KB
• Volume: 28
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(02)00135-7

✦ Synopsis

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 [6] 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.