Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille

C. Prins

RAIRO - Operations Research - Recherche Opérationnelle (1996)

  • Volume: 30, Issue: 4, page 333-357
  • ISSN: 0399-0559

How to cite

top

Prins, C.. "Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille." RAIRO - Operations Research - Recherche Opérationnelle 30.4 (1996): 333-357. <http://eudml.org/doc/105133>.

@article{Prins1996,
author = {Prins, C.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {shortest paths; large sparse graphs; road-like networks},
language = {fre},
number = {4},
pages = {333-357},
publisher = {EDP-Sciences},
title = {Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille},
url = {http://eudml.org/doc/105133},
volume = {30},
year = {1996},
}

TY - JOUR
AU - Prins, C.
TI - Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 4
SP - 333
EP - 357
LA - fre
KW - shortest paths; large sparse graphs; road-like networks
UR - http://eudml.org/doc/105133
ER -

References

top
  1. 1. R. K. AHUJA, K. MELHORN, J. B. ORLIN et R. E. TARJAN, Faster algorithms for the shortest path problem, Technical Report 193, MIT Operations Research Center, 1988. Zbl0696.68046
  2. 2. D. BEAUQUIER, J. BERSTEL et Ph. CHRÉTIENNE, Éléments d'algorithmique, Masson, 1992. 
  3. 3. T. H. CORMEN, C. L. LEISERSON, R. L. RIVEST, Introduction to algorithms, The MIT Press, 1992. Zbl1158.68538
  4. 4. E. DENARDO et B. Fox, Shortest-route methods. 1. Reaching, pruning and buckets, Operations Research, 1979, 27, p. 161-186. Zbl0391.90089MR519570
  5. 5. R. DIAL, Algorithm 360: Shortest path forest with topological ordering, Communications of the ACM, 1969, 72, p. 632-633. 
  6. 6. J. J. DIVOKY, M. S. HUNG, Performance of shortest path algorithms in network flow problems, Management Science, 1990, 36, (6), p.661-673. Zbl0699.90031MR1059218
  7. 7. G. N. FREDERICKSON, Fast algorithms for shortest paths in planar graphs with applications, SIAM Journal on Computing, 1987, 16, (6), p. 1004-1022. Zbl0654.68087MR917037
  8. 8. F. GLOVER, R. GLOVER et D. KLINGMAN, Computational study of an improved shortest path algorithm, Networks, 1984, 14, p. 25-36. 
  9. 9. F. GLOVER, D. KLINGMAN et N. V. PHILLIPS, A new polynomially bounded shortest path algorithm, Opérations Research, 1985, 33, (1), p.65-73. Zbl0578.90089MR786047
  10. 10. F. GLOVER, D. KLINGMAN, N. V. PHILLIPS et R. F. SCHNEIDER, New polynomial shortest path algorithms and their computational attributes, Management Science, 1985, 31, (9), p. 1106-1129. Zbl0609.90103MR821400
  11. 11. M. GONDRAN et M. MINOUX, Graphes et Algorithmes, Eyrolles, 1979. Zbl0497.05023MR615739
  12. 12. M.S. HUNG et J. J. DIVOKY, A computational study of efficient shortest path algorithms, Computers and Operations Research, 1988, 15, (6), p. 567-576. Zbl0659.90087MR974886
  13. 13. D. KLINGMAN, R. F. SCHNEIDER, Microcomputer-based algorithms for large scale shortest path problems, Discrete Applied Mathematics, 1986, 73, p. 183-206. Zbl0586.90086MR837940
  14. 14. M. MINOUX, Programmation mathématique, Masson, 1983 (2 volumes). Zbl0546.90056
  15. 15. J. A. MCHUGH, Algorithmic graph theory, Prentice Hall, 1990. Zbl0755.68056
  16. 16. U. PAPE, Algorith 562: shortest path lengths, ACM Trans. Math. Software, 1980, 5, p.450-455. Zbl0442.68063
  17. 17. J. PEARL, Heuristics, Addison-Wesley, 1984. 
  18. 18. C. PRINS, Calcul sur micro-ordinateur de plus courts chemins dans les grands graphes peu denses, Rapport DAP-93-11, Département d'Automatique et Productique, École des Mines de Nantes. 
  19. 19. R. SEDGEWICK et J. S. VITTER, Shortest paths in euclidean graphs, Algorithmica, 1986, 1, p. 31-48. Zbl0611.68044MR833117
  20. 20. M. SYSLO, N. DEO et J. S. KOWALIK, Discrete optimization algorithms with Pascal programs, Prentice Hall, 1993. Zbl0574.90057
  21. 21. R. E. TARJAN, Data structures and network algorithms, SIAM, 1983. Zbl0584.68077MR826534

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.