Published October 1997
| public
Book Section - Chapter
Hamiltonian cycles in solid grid graphs
- Creators
- Umans, Christopher
- Lenhart, William
Abstract
A grid graph is a finite node induced subgraph of the infinite two dimensional integer grid. A solid grid graph is a grid graph without holes. For general grid graphs, the Hamiltonian cycle problem is known to be NP complete. We give a polynomial time algorithm for the Hamiltonian cycle problem in solid grid graphs, resolving a longstanding open question posed by A. Itai et al. (1982). In fact, our algorithm can identify Hamiltonian cycles in quad quad graphs, a class of graphs that properly includes solid grid graphs.
Additional Information
© 1997 IEEE. Date of Current Version: 06 August 2002. Research supported in part by an NSF Graduate Research Fellowship. We would like to thank Christos Papadimitriou for several useful comments on an earlier draft of this paper.Additional details
- Eprint ID
- 28978
- Resolver ID
- CaltechAUTHORS:20120126-092849476
- NSF Graduate Research Fellowship
- Created
-
2012-01-26Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 5809396