THE HAMILTON CIRCUIT PROBLEM ON GRIDS

Authors
AFRATI F
Citation
F. Afrati, THE HAMILTON CIRCUIT PROBLEM ON GRIDS, Informatique theorique et applications, 28(6), 1994, pp. 567-582
Citations number
11
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
Journal title
Informatique theorique et applications → ACNP
ISSN journal
09883754
Volume
28
Issue
6
Year of publication
1994
Pages
567 - 582
Database
ISI
SICI code
0988-3754(1994)28:6<567:THCPOG>2.0.ZU;2-3
Abstract
This paper investigates the Hamilton circuit problem on grid graphs. F or general grid graphs it is known to be NP-complete. We consider a no n-trivial subclass of grid graphs and present a linear algorithm for f inding a Hamilton circuit. Moreover, we show that our algorithm can be optimally parallelized, hence the problem belongs to NC.