The Hamilton circuit problem on grids
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1994)
- Volume: 28, Issue: 6, page 567-582
- ISSN: 0988-3754
Access Full Article
top
How to cite
topAfrati, Foto. "The Hamilton circuit problem on grids." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.6 (1994): 567-582. <http://eudml.org/doc/92494>.
@article{Afrati1994,
author = {Afrati, Foto},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Hamilton circuit problem; grid graphs},
language = {eng},
number = {6},
pages = {567-582},
publisher = {EDP-Sciences},
title = {The Hamilton circuit problem on grids},
url = {http://eudml.org/doc/92494},
volume = {28},
year = {1994},
}
TY - JOUR
AU - Afrati, Foto
TI - The Hamilton circuit problem on grids
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 6
SP - 567
EP - 582
LA - eng
KW - Hamilton circuit problem; grid graphs
UR - http://eudml.org/doc/92494
ER -
References
top- 1. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The design and Analysis of Computer Algorithms, Addision Wesley, Reading MA., 1974. Zbl0326.68005MR413592
- 2. M. GAREY and D. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman & Company, San Fransisco, 1979. Zbl0411.68039MR519066
- 3. A. ITAI, C. H. PAPADIMITRIOU and J. SZWARCFITER, Hamilton paths in grid graphs, SIAM J. Computing, November 1982, 11, 4, pp. 676-686. Zbl0506.05043MR677661
- 4. R. M. KARP and V. RAMACHANDRAN, A survey of parallel algorithms for shared-memory machines, Technical Report CSD 88/408, UCB, 1988. Zbl0900.68267
- 5. D. ANGLUIN and L. VALIANT, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings, J. Computer Syst., 1979, 18, pp. 155-193. Zbl0437.05040MR532174
- 6. C. BERGE, Graphs and Hypergraphs, North-Holland-American Elsevier, 1973. Zbl0254.05101MR357172
- 7. B. BOLLOBAS, Extremal Graph Theory, Academic Press, London 1978. Zbl0419.05031MR506522
- 8. A. M. FRIEZE, Parallel Algorithms for finding Hamiltonian Cycles in Random Graphs, Information Processing Letters, 1987, 25, pp. 111-117. Zbl0653.68071MR896153
- 9. D. SOROKER, Fast Parallel Algorithms for finding Hamiltonian Paths and Cycles in a Tournament, Technical Report No. UCB/CSD 87/309, University of California, Berkeley 1986. Zbl0644.05036MR936110
- 10. E. DAHLHAUS, P. HAJNAL and M. KARPINSKI, Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs, Proceedings 29th IEEE FOCS, 1988, pp. 186-193.
- 11. J. SILVESTER and L. KLEINROCK, On the Capacity of Multihop slottee ALOHA Networks with Regular Structure, IEEE Transactions on Communications, COM-31, August 1983, pp. 974-982.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.