Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
NIST Authors in Bold
|Author(s):||William F. Mitchell;|
|Title:||Hamiltonian Paths Through Two- and Three-Dimensional Grids|
|Published:||April 01, 2005|
|Abstract:||This paper addresses the existence of Hamiltonian paths and cycles in two-dimensional grids consisting of triangles or quadrilaterals, and three-dimensional grids consisting of tetrahedra or hexahedra. The paths and cycles may be constrained to pass from one element to the next through an edge, through a vertex, or be unconstrained and pass through either. It was previously known that an unconstrained Hamiltonian path exists in a triangular grid under very mild conditions, and that there are triangular grids for which there is no through-edge Hamiltonian path. In this paper we prove that a through-vertex Hamiltonian cycle exists in any triangular or tetrahedral grid under very mild conditions, and that there exist quadrilateral and hexahedral grids for which no unconstrained Hamiltonian path exists. The existence proofs are constructive, and lead to an efficient algorithm for finding a through-vertex Hamiltonian cycle.|
|Citation:||Journal of Research (NIST JRES) - of|
|Volume:||110 No. 2|
|Keywords:||adaptive grid refinement,Hamiltonian path,load balancing,refinement-tree partition|
|PDF version:||Click here to retrieve PDF version of paper (900KB)|