On the difficulty of finding walks of length k
Basagni, S. ; Bruschi, D. ; Ravasio, F.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 429-435 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1997-01-01
@article{ITA_1997__31_5_429_0,
     author = {Basagni, S. and Bruschi, D. and Ravasio, F.},
     title = {On the difficulty of finding walks of length k},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {429-435},
     mrnumber = {1611647},
     zbl = {0893.68072},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_5_429_0}
}

Basagni, S.; Bruschi, D.; Ravasio, F. On the difficulty of finding walks of length k. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 429-435. http://gdmltest.u-ga.fr/item/ITA_1997__31_5_429_0/

1. N. Alon, R. Yuster and U. Zwick, Color-coding, Journal of the ACM, 1995, 42, 4, pp. 844-856. | MR 1411787 | Zbl 0885.68116

2. F. Barahona and W. R. Pulleyblank, Exact arborescences, matchings and cycles. Discrete Applied Mathematics, 1987, 16, pp. 91-99. | MR 874908 | Zbl 0632.05047

3. D. Bruschi and F. Ravasio, Random parallel algorithms for findings cycles, branchings and perfect matchings. Algorithmica, 1995, 13, 4, pp. 346-356. | Zbl 0827.68052

4. P. M. Camerini, G. Galbiati and F. Maffioli, Random pseudo-polynomial algorithms for exacts matroid problems. Journal of Algorithms, 1992, 13, 2, pp. 258-273. | Zbl 0773.05032

5. T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990. | Zbl 1158.68538

6. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979. | Zbl 0411.68039

7. Y. Han, V. Pan and J. Reif, Efficient parallel algorithms for computing all pair shortest paths in directed graphs. In Proc. 4th ACM Symp. on Parallel Algorithms and Architectures, 1992, pp. 353-362.

8. A. Kaufmann, Graphs, dynamic programming and finite games. Academic Press, New York, 1967. Translation of v. 2 of Methodes et modèles de la recherche. | Zbl 0161.39201

9. E. L. Lawler, Combinatorial Optimization: Networks and Matroids. Holt Rinehart and Winston, New York, 1976. | MR 439106 | Zbl 0413.90040

10. C. H. Papadimitriou and M. Yannakakis, The complexity of restricted spanning tree problems. Journal of the ACM, 1982, 29, 2, pp. 285-309. | MR 651671 | Zbl 0478.68068

11. W. Tutte. Graph Theory, Addison-Wesley, Reading, MA, 1984. | MR 746795