On the difficulty of finding walks of length k
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) no. 5, pp. 429-435.
@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},
pages = {429--435},
publisher = {EDP-Sciences},
volume = {31},
number = {5},
year = {1997},
zbl = {0893.68072},
mrnumber = {1611647},
language = {en},
url = {http://www.numdam.org/item/ITA_1997__31_5_429_0/}
}
TY  - JOUR
AU  - Basagni, S.
AU  - Bruschi, D.
AU  - Ravasio, F.
TI  - On the difficulty of finding walks of length k
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1997
DA  - 1997///
SP  - 429
EP  - 435
VL  - 31
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1997__31_5_429_0/
UR  - https://zbmath.org/?q=an%3A0893.68072
UR  - https://www.ams.org/mathscinet-getitem?mr=1611647
LA  - en
ID  - ITA_1997__31_5_429_0
ER  - 
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) no. 5, pp. 429-435. http://www.numdam.org/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