# On the difficulty of finding walks of length k

S. Basagni; D. Bruschi; F. Ravasio

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)

- Volume: 31, Issue: 5, page 429-435
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topBasagni, S., Bruschi, D., and Ravasio, F.. "On the difficulty of finding walks of length k." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 31.5 (1997): 429-435. <http://eudml.org/doc/92570>.

@article{Basagni1997,

author = {Basagni, S., Bruschi, D., Ravasio, F.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {computational complexity; directed graph},

language = {eng},

number = {5},

pages = {429-435},

publisher = {EDP-Sciences},

title = {On the difficulty of finding walks of length k},

url = {http://eudml.org/doc/92570},

volume = {31},

year = {1997},

}

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

PB - EDP-Sciences

VL - 31

IS - 5

SP - 429

EP - 435

LA - eng

KW - computational complexity; directed graph

UR - http://eudml.org/doc/92570

ER -

## References

top- 1. N. ALON, R. YUSTER and U. ZWICK, Color-coding, Journal of the ACM, 1995, 42, 4, pp. 844-856. Zbl0885.68116MR1411787
- 2. F. BARAHONA and W. R. PULLEYBLANK, Exact arborescences, matchings and cycles. Discrete Applied Mathematics, 1987, 16, pp. 91-99. Zbl0632.05047MR874908
- 3. D. BRUSCHI and F. RAVASIO, Random parallel algorithms for findings cycles, branchings and perfect matchings. Algorithmica, 1995, 13, 4, pp. 346-356. Zbl0827.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. Zbl0773.05032
- 5. T. H. CORMEN, C. E. LEISERSON and R. L. RIVEST, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990. Zbl1158.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. Zbl0411.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. Zbl0161.39201
- 9. E. L. LAWLER, Combinatorial Optimization: Networks and Matroids. Holt Rinehart and Winston, New York, 1976. Zbl0413.90040MR439106
- 10. C. H. PAPADIMITRIOU and M. YANNAKAKIS, The complexity of restricted spanning tree problems. Journal of the ACM, 1982, 29, 2, pp. 285-309. Zbl0478.68068MR651671
- 11. W. TUTTE. Graph Theory, Addison-Wesley, Reading, MA, 1984. Zbl0554.05001MR746795

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.