# zbMATH — the first resource for mathematics

An efficient algorithm for constructing Hamiltonian paths in meshes. (English) Zbl 0999.68253
Summary: 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.

##### MSC:
 68W10 Parallel algorithms in computer science
Full Text: