Algèbre linéaire et cheminement dans un graphe

 Access to full text

 Full (PDF)

1. [1] BELLMAN R., « On a routing problem , Quart. Appl. Math., 16 (1958). Zbl0081.14403MR102435
2. [2] BENZAKEN C., « Structures algébriques des cheminements : pseudo-treillis, gerbier de carré nul », in Network and Switching Theory, edited by G. Biorci, Academic Press, 1968, p.40-47. Zbl0285.06005
3. [3] BERGE C., « Théorie des graphes et ses applications », Dunod, Paris, 1958 Zbl0121.40101MR102822
4. [4] CARRÉ B. A., « An algebra for network routing problems », J. Inst Maths. Applics, 7 (1971), p. 273-294. Zbl0219.90020MR292583
5. [5] DANTZIG G.B., « All shortest routes in a graph », Proc. I.C.C. Conference on Teory of Graphs, Rome (1966), Gordon and Breach, N.Y., p. 91-92. Zbl0189.24104MR221981
6. [6] FLOYD R.W., « Algorithm 97 : Shortest path », Communication of ACM, Vol. 5 (1962), p. 345. 
7. [7] FORD L. R. and FULKERSON D. R., « Flows in Network », Princeton University Press, 1962. Zbl1216.05047MR159700
8. [8] FORTET R., « L'algèbre deBoole et ses applications enRecherche Opérationnelle », Cahier du Centre d'Études de R.O., Bruxelles, 1959, n° 4. Zbl0093.32704MR114782
9. [9] GONDRAN M., « Fiabilité dans les réseaux », note EDF à paraître. 
10. [10] GRASSIN J. et MINOUX M., « Variations sur un algorithme de Dantzig. Application à la recherche des plus courts chemins dans les grands réseaux », R.A.I.R.O., 7 année (1973), V1, p. 53-62. Zbl0259.90052MR327569
11. [11] HOFFMAN A. J. and WINOGRAD S., « Finding all shortest Distances in a directed Network », IBM J. Res. Develop., 1973. Zbl0276.90059MR345723
12. [12] HU T. C., «A decomposition algorithm for shortest paths in a network», Operations Research, 16 (1968), n° 1, p. 91-102. Zbl0155.28802
13. [13] KAUFMAN A. et MALGRANGE Y., « Recherche des chemins et circuits hamiltoniens d'un graphe », Revue Française de R.Q., 7 année (1963), n° 26, p. 61-73. 
14. [14] KNUTH D. E., « The art of Computer Programming », vol. 2, Seminumerical algorithme Addison-Wesley, 1969, p. 398-422. MR286318
15. [15] KUNTZMANN J., « Théorie des relations et des réseaux », Cours, Université de Grenoble, 1966. 
16. [16] MAGHOUT K., « Applications de l'algèbre de Boole à la théorie des graphes et aux problèmes linéaires et quadratiques », Cahiers du Centre d'Études et de R.O., Bruxelles, tome 5 (1963), n° 1-2, p. 21-99. Zbl0114.12102MR158762
17. [17] NOLIN I., « Traitement des données groupées », Publication de l'Institut Blaise Pascal, Paris, mai 1964. 
18. [18] PAIR C. et DERNIAME J. C., « Étude des problèmes de cheminement dans les graphes finis », Convention D.G.R.S.T., n° 66-002. Zbl0243.05117
19. [18] ] PETEANU V., «An algebra of the optimal path in networks», Mathematica, vol 9 (1967), n° 2, p. 335-342. Zbl0171.15305MR231664
20. [20] PICHAT E., « Algorithms for finding the maximal elements of a finite universal algebra », Proc. IFIP Congress 1968, Edinburg, Booklet A, p. 96-101 Zbl0204.33201
21. [21] ROBERT P. and FERLAND J., « Généralisation de l'algorithme de Warshall », Rev. Française Informatique et R.O. (1968), n° 7, p. 71-85. Zbl0172.20601MR234770
22. [22] ROY B., « Transitivité et connexité », C.R. Acad. Sciences Paris, tome 249 (1959) p. 216. Zbl0092.15902MR109792
23. [23] ROY B., « Algèbre moderne et théorie des graphes », Dunod, Paris, 1970, tome 2. Zbl0238.90073MR260413
24. [24] TABOURIER Y., « All shortest distances in a graph. An improvement to Dantzig's inductive algorithm », Discrete Mathematics, 4 (1973), p. 83-87. Zbl0257.05128MR313117
25. [25] TOMESCU I., « Sur les méthodes matricielles dans la théorie des réseaux », C.R. Acad Sci. Paris, tome 263 (1966), p. 826-829. Zbl0152.14702MR207395
26. [26] TOMESCU I., « Un algorithme pour la détermination des plus petites distances entre les sommets d'un réseau », R.I.R.O., 1e année (1967), 5, p. 133-139. Zbl0155.28803MR224360
27. [27] WARSHALL S., « A theorem on boolean Matrices », J. of ACM, vol. 9 (1962), p. 11-12. Zbl0118.33104MR149688
28. [28] CRUON R. et HERVÉ P., « Quelques résultats relatifs à une structure algébrique et son application au problème central de l'ordonnancement », Revue Française de R.O., n°34, 1965, p. 3-19. Zbl0143.42002
29. [29] COFFY et GONDRAN, « Note sur le problème du k-ième plus court chemin », à paraître. 
30. [30] GONDRAN M., « Algèbre des chemins et algorithmes », note EDF, HI 1753/02 du 10 août 1974, MR476574
31. [30] GONDRAN M. à paraître en anglais sous le titre « Path Algebra and Algorithms » dans « Combinatorial Programming : Methods and Applications », B. Roy éditeur, D. Reidel Publishing Co., Dordrecht, Hollande (1975). 
32. [31] GONGRAN M., « Les algorithmes dans les algèbres de chemins », à paraître dans le Bulletin des Etudes et Recherches EDF, 1975. 
33. [32] SHIER D. R., « A decomposition algorithm for optimality problems in tree-structured networks », Discute Mathematics 6, 1973, p. 175-189. Zbl0298.90058MR334955

1. J. Fonlupt, L'affectation exponentielle et le problème du plus court chemin dans un graphe
2. M. Gondran, Valeurs propres et vecteurs propres en classification hiérarchique