Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/36767
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | An efficient algorithm for constructing Hamiltonian paths in meshes |
Author: | Dong, C. Shen, H. Topor, R. |
Citation: | Parallel Computing, 2002; 28(11):1293-1305 |
Publisher: | Elsevier Science BV |
Issue Date: | 2002 |
ISSN: | 0167-8191 |
Statement of Responsibility: | Shao Dong Chen, Hong Shen, and Rodney Topor |
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 [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. |
Keywords: | Hamiltonian paths Meshes Sequential and parallel algorithms Performance evaluation |
Description: | Copyright © 2002 Elsevier Science B.V. All rights reserved. |
DOI: | 10.1016/S0167-8191(02)00135-7 |
Description (link): | http://www.elsevier.com/wps/find/journaldescription.cws_home/505617/description#description |
Published version: | http://dx.doi.org/10.1016/s0167-8191(02)00135-7 |
Appears in Collections: | Aurora harvest 6 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.