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. https://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: https://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: |
| |||||||||
| DOI: | 10.1109/SFCS.1997.646138 | |||||||||
| Record Number: | CaltechAUTHORS:20120126-092849476 | |||||||||
| Persistent URL: | https://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: | 09 Nov 2021 17:02 |
Repository Staff Only: item control page
