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
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|
|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.|
|Other Numbering System:|
|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.|
|Deposited By:||Tony Diaz|
|Deposited On:||26 Jan 2012 23:13|
|Last Modified:||26 Jan 2012 23:13|
Repository Staff Only: item control page