Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
RAIRO - Operations Research - Recherche Opérationnelle (1985)
- Volume: 19, Issue: 1, page 57-69
- ISSN: 0399-0559
Access Full Article
top
How to cite
topLavallée, I.. "Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe." RAIRO - Operations Research - Recherche Opérationnelle 19.1 (1985): 57-69. <http://eudml.org/doc/104870>.
@article{Lavallée1985,
author = {Lavallée, I.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {parallel algorithms; mutual exclusion; minimum spanning tree; valued undirected graph},
language = {fre},
number = {1},
pages = {57-69},
publisher = {EDP-Sciences},
title = {Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe},
url = {http://eudml.org/doc/104870},
volume = {19},
year = {1985},
}
TY - JOUR
AU - Lavallée, I.
TI - Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1985
PB - EDP-Sciences
VL - 19
IS - 1
SP - 57
EP - 69
LA - fre
KW - parallel algorithms; mutual exclusion; minimum spanning tree; valued undirected graph
UR - http://eudml.org/doc/104870
ER -
References
top- 1. J. L. BENTLEY, A Parallel Algorithm for Constructing Minimum Spanning Trees, Journal of algorithms vol. 1, 1980, p. 51-59. Zbl0435.68049MR578076
- 2. C. BERGE et A. GHOUILA HOURI, Programmes, jeux et réseaux de transport, Dunod, Paris, 1962. Zbl0111.17302MR192912
- 3. C. BERGE, Graphes & hypergraphes, Dunod, Paris, 1973, 2e édition. Zbl0332.05101MR898652
- 4. Per. BRINCH HANSEN, Distribued Processes=A Concurrent Programming Concept, CACM, vol. 21, n° 11, 1978, p. 934-941. Zbl0393.68028
- 5. Q. S. F. CARVALHO et G. ROUCAIROL, Une amélioration de l'algorithme d'exclusion mutuelle de Ricart et Agrawala, L.I.T.P. Internal Report n° 81-58, novembre 1981.
- 6. Q. S. F. CARVALHO et G. ROUCAIROL, On Mutual Exclusion in Computer Networks, Technical correspondance, CACM, vol. 26, n° 2, février 1983.
- 7. R. FAURE, Précis de Recherche Opérationnelle, Dunod, Paris, 1979.
- 8. I. LAVALLÉE, Notes sur le parallélisme, C.N.R.S.-G.R. Claude François Picard, Tour 45, 4, place Jussieu, 75230 Paris Cedex 05, 1983.
- 9. I. LAVALLÉE, "An efficient parallel algorithm for Computing a minimal spanning tree", Parallel Computing 83, Elsevier Science Publishers, B.V. (North-Holland) pp. 259-262, 1984. MR809404
- 10. F. MAFFIOLI, Complexity of Optimum Undirected Tree Problems, Analysis and Design of Algorithms in Combinatorial Optimization, G. AUSIELLO et M. LUCERTINI éd., Springer-Verlag, 1981.
- 11. R. C. PRIM, Shortest Connections Networks and Some Generalizations, Bell System Tech. J., vol. 36, 1957, p. 1389-1401.
- 12. C. SAVAGE et J. J JA'JA, Fast, Efficient Parallel Algorithms for Some Graph Problems, S.I.A.M. J. on Computing, vol. 10, n° 4, novembre 1981, p. 682-691. Zbl0476.68036MR635426
- 13. M. SOLLIN, Exposé du Séminaire de C. Berge, I.H.P., 1961; repris in extenso dans Méthodes et modèles de la R.O. », t. 2, p. 33-45, A. KAUFMANN éd., Dunod, Paris, 1968.
- 14. D. STOTT PERKER et B. SAMADI, Distributed Minimal Spanning Tree Algorithms, Performances of data communication System and their applications, G. PUJOLLE éd., North Holland Publishing Company, 1981, p. 46-53.
- 15. G. RICART et A. AGRAWALA, An Optimal Algorithm for Mutual Exclusion in Computer Networks, Comm. A.C.M. 24.1, janvier 1981, p. 9-17. On trouvera une bibliographie très complète dans [14]. MR600729
NotesEmbed ?
topYou 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.