Umans, Christopher and Lenhart, William
(1997)
*Hamiltonian cycles in solid grid graphs.*
In:
38th Annual Symposium on Foundations of Computer Science: Proceedings.
Los Alamitos, CA
, IEEE Computer Society Press, pp. 496-505.
ISBN 0-8186-8197-7
http://resolver.caltech.edu/CaltechAUTHORS:20120126-092849476

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120126-092849476

## 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.

Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| |||||||||

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. | |||||||||

Funders: |
| |||||||||

Other Numbering System: |
| |||||||||

Record Number: | CaltechAUTHORS:20120126-092849476 | |||||||||

Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20120126-092849476 | |||||||||

Official Citation: | Umans, C.; Lenhart, W.; , "Hamiltonian cycles in solid grid graphs," Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on , vol., no., pp.496-505, 20-22 Oct 1997 doi: 10.1109/SFCS.1997.646138 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=646138&isnumber=14088 | |||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||

ID Code: | 28978 | |||||||||

Collection: | CaltechAUTHORS | |||||||||

Deposited By: | Tony Diaz | |||||||||

Deposited On: | 26 Jan 2012 23:13 | |||||||||

Last Modified: | 26 Jan 2012 23:13 |

Repository Staff Only: item control page