recherche d’arbre couvrant de poids minimum
Histoire
Otakar Borůvka (né le 10 mai 1899 à Uherský Ostroh – mort le 22 juillet 1995 à Brno en Tchécoslovaquie) était ingénieur en télécommunication.
En 1926, il écrit un premier article “O jistém problému minimálním” dans lequel il décrit un algorithme permettant de trouver un arbre couvrant de poids minimum dans un réseau de distribution électrique.
Son premier article, jamais publié, est redécouvert par Gustave Choquet en 1938 puis par George Sollin en 1961.
Les algorithmes de Prim et Kruskal seront proposés en 1956 et citeront l’algorithme de Boruvka.
Dorian vous conseille de lire l’article de R. L. Graham et Pavol Hell intitulé “On the history on the MST problem“.
Algorithme
L’algorithme de Borůvka s’applique sur des graphes valués dont les poids des arêtes sont tous différents.
Note
L’algorithme de Bernard Chazelle (2000) utilise celui de Borůvka, tout comme pour celui de Kroeger, Klein et Tarjan.
Bibliographie conseillée
R.L. Graham, Pavol Hell, “On the History of the Minimum Spanning Tree Problem,” IEEE Annals of the History of Computing, vol. 7, no. 1, pp. 43-57, Jan.-Mar. 1985, doi:10.1109/MAHC.1985.10011