The Hamilton circuit problem on grids
Afrati, Foto
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 567-582 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@article{ITA_1994__28_6_567_0,
     author = {Afrati, Foto},
     title = {The Hamilton circuit problem on grids},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {567-582},
     mrnumber = {1305117},
     zbl = {0884.68097},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_6_567_0}
}

Afrati, Foto. The Hamilton circuit problem on grids. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 567-582. http://gdmltest.u-ga.fr/item/ITA_1994__28_6_567_0/

1. A. V. Aho, J. E. Hopcroft and J. D. Ullman, The design and Analysis of Computer Algorithms, Addision Wesley, Reading MA., 1974. | MR 413592 | Zbl 0326.68005

2. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman & Company, San Fransisco, 1979. | MR 519066 | Zbl 0411.68039

3. A. Itai, C. H. Papadimitriou and J. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Computing, November 1982, 11, 4, pp. 676-686. | MR 677661 | Zbl 0506.05043

4. R. M. Karp and V. Ramachandran, A survey of parallel algorithms for shared-memory machines, Technical Report CSD 88/408, UCB, 1988.

5. D. Angluin and L. Valiant, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings, J. Computer Syst., 1979, 18, pp. 155-193. | MR 532174 | Zbl 0437.05040

6. C. Berge, Graphs and Hypergraphs, North-Holland-American Elsevier, 1973. | MR 357172 | Zbl 0254.05101

7. B. Bollobas, Extremal Graph Theory, Academic Press, London 1978. | MR 506522 | Zbl 0419.05031

8. A. M. Frieze, Parallel Algorithms for finding Hamiltonian Cycles in Random Graphs, Information Processing Letters, 1987, 25, pp. 111-117. | MR 896153 | Zbl 0653.68071

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. | MR 936110

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.