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

How to cite

top

Basagni, 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. 1. N. ALON, R. YUSTER and U. ZWICK, Color-coding, Journal of the ACM, 1995, 42, 4, pp. 844-856. Zbl0885.68116MR1411787
  2. 2. F. BARAHONA and W. R. PULLEYBLANK, Exact arborescences, matchings and cycles. Discrete Applied Mathematics, 1987, 16, pp. 91-99. Zbl0632.05047MR874908
  3. 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. 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. 5. T. H. CORMEN, C. E. LEISERSON and R. L. RIVEST, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990. Zbl1158.68538
  6. 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. 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. 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. 9. E. L. LAWLER, Combinatorial Optimization: Networks and Matroids. Holt Rinehart and Winston, New York, 1976. Zbl0413.90040MR439106
  10. 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. 11. W. TUTTE. Graph Theory, Addison-Wesley, Reading, MA, 1984. Zbl0554.05001MR746795

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.