CaltechAUTHORS
  A Caltech Library Service

Hamiltonian cycles in solid grid graphs

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:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.1997.646138DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=646138PublisherUNSPECIFIED
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:
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number5809396
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