Geodesic
A few remarks on the history of MST-problem
Archivum mathematicum, Tome 33 (1997) no. 1-2, pp. 15-22
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

On the background of Borůvka’s pioneering work we present a survey of the development related to the Minimum Spanning Tree Problem. We also complement the historical paper Graham-Hell [GH] by a few remarks and provide an update of the extensive literature devoted to this problem.
On the background of Borůvka’s pioneering work we present a survey of the development related to the Minimum Spanning Tree Problem. We also complement the historical paper Graham-Hell [GH] by a few remarks and provide an update of the extensive literature devoted to this problem.
Classification : 01-01, 01A60, 01A70, 05C05 
@article{ARM_1997_33_1-2_a3,
     author = {Ne\v{s}et\v{r}il, Jaroslav},
     title = {A few remarks on the history of {MST-problem}},
     journal = {Archivum mathematicum},
     pages = {15--22},
     year = {1997},
     volume = {33},
     number = {1-2},
     mrnumber = {1464297},
     zbl = {0909.05022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ARM_1997_33_1-2_a3/}
}
TY  - JOUR
AU  - Nešetřil, Jaroslav
TI  - A few remarks on the history of MST-problem
JO  - Archivum mathematicum
PY  - 1997
SP  - 15
EP  - 22
VL  - 33
IS  - 1-2
UR  - http://geodesic.mathdoc.fr/item/ARM_1997_33_1-2_a3/
LA  - en
ID  - ARM_1997_33_1-2_a3
ER  - 
%0 Journal Article
%A Nešetřil, Jaroslav
%T A few remarks on the history of MST-problem
%J Archivum mathematicum
%D 1997
%P 15-22
%V 33
%N 1-2
%U http://geodesic.mathdoc.fr/item/ARM_1997_33_1-2_a3/
%G en
%F ARM_1997_33_1-2_a3
Nešetřil, Jaroslav. A few remarks on the history of MST-problem. Archivum mathematicum, Tome 33 (1997) no. 1-2, pp. 15-22. http://geodesic.mathdoc.fr/item/ARM_1997_33_1-2_a3/

[Bo1] O. Borůvka: O jistém problému minimálním (About a certain minimal problem). Práce mor. přírodověd. spol. v Brně III, 3 (1926), 37–58.

[Bo2] O. Borůvka: Příspěvek k řešení otázky ekonomické stavby elektrovodných sítí (Contribution to the solution of a problem of economical construction of electrical networks). Elektrotechnický obzor 15(1926), 153–154.

[C] K. Čulík: K jednomu minimálnímu problému O. Borůvky. Čas. pro pěst. mat. 85(1960), 93–94.

[CDF] K. Čulík, V. Doležal, M. Fiedler: Kombinatorická analýza v praxi. SNTL, Prague, 1967.

[CKT] R. Cole, P. N. Klein, R. E. Tarjan: A linear-work parallel algorithm for finding minimum spanning trees. Proc. of SPAA, 1994.

[Da] G. Dantzig: Discrete variable extremum problems. Oper. Research 5(1957). | MR

[Di] E. W. Dijkstra: Some theorems on spanning subtrees of a graph. Indag. Math. XXII, 2(1960), 196–199. | MR | Zbl

[DRT] B. Dixon, M. Rauch, R. Tarjan: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. of Computing 21, 6(1992), 1184–1192. | MR

[E] J. Edmonds: Optimum branchings. J. Res. Nat. Bur. Standards 71B(1967), 233–240. | MR | Zbl

[FW] M. Fredman, D. E. Willard: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Proc. 31st Annual IEEE Symp. on Found. of Comp. Sci., 1966, 719–725.

[FT] M. Fredman, R. E. Tarjan: Fibonacci heaps and their uses in network optimization algorithms. Proc. 25th Annual IEEE Symp. on Found. of Comp. Sci., 1984, 338–346.

[GGS] H. N. Gabov, Z. Galil, T. H. Spencer: Efficient implementation of graph algorithms using contraction. Proc. 25th Annual IEEE Symp. on Foundations of Computer Sci., 1984, 347–357.

[GGST] H. N. Gabov, Z. Galil, T. H. Spencer, R. E. Tarjan: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(1986), 109–122. | MR

[GH] R. L. Graham, P. Hell: On the history of the minimum spanning tree problem. Annals of the History of Computing 7(1985), 43–57. | MR

[Ja] V. Jarník: O jistém problému minimálním. Práce mor. přírodověd. spol. v Brně VI, 4(1930), 57–63.

[JK] V. Jarník, M. Kössler: O minimálních grafech obsahujících $n$ daných bodů. Čas. pro pěst. mat. 63(1934), 223–235.

[K] R. Kalaba: On some communication network problem. Proc. Symp. Applied Math. (1960), 261–280. | MR

[Ka] D. R. Karger: Random sampling in matroids, with applications to graph connectivity and minimumspanning trees. Proc. 34th Annual IEEE Symp. on Found. of Computer Sci. 1993, 84–93. | MR

[KKT] D. Karger, P. N. Klein, R. E. Tarjan: A randomized linear-time algorithm to find minimum spanning trees. J. Assoc. Comp. Mach. 42(1995), 321–328. | MR

[Ki] V. King: A simpler minimum spanning tree verification algorithm. manuscript 1993. | Zbl

[KT] P. N. Klein, R. E. Tarjan: A randomized linear-time algorithm for finding minimum spanning trees. Proc. 26th Annual ACM Symp. on theory of Computing, 1994, 9–15.

[Ko] J. Komlos: Linear verification for spanning trees. Combinatorica 5(1985), 57–65. | MR | Zbl

[KLS] B. Korte, L. Lovasz, R. Schrader: Greedoids. Springer Verlag (1991). | MR

[KN] B. Korte, J. Nešetřil: Vojtěch Jarník’s work in combinatorial optimization. KAM Series No. 96–315.

[Ko] A. Kotzig: Súvislé grafy s minimálnou hodnotou v konečnom súvislom grafe. Čas pro pěst. mat. (1961), 1–6. | MR

[Kr] J. B. Kruskal: On the shortest spanning subtree of a graph and the travelling salesman problem. Proc. Amer. Math. Soc. 7(1956), 48–50. | MR

[LFPSZ] J. Lukasiewicz, K. Florek, J. Perkal. H. Steinhaus, S. Zubrzycky: Sur la liaison et la division des points d’un ensemble fini. Colloq. Math. 2(1949-1951), 282–285. | MR

[M] E. Milková: Prohledávání, třídění a optimalizace stromů. doctoral dissertation, Prague, 1997.

[Pr] R. C. Prim: The shortest connecting network and some generalisations. Bell. Syst. Tech. J. 36(1957), 1389–1401.

[So] E. W. Solomon: A comprehensive program for network problems. Computer J. 3(1960), 89–97. | MR

[Ta1] R. E. Tarjan: Data structures and network algorithms. CBMS-NSF Regional Conf. Series in Applied Math., SIAM 44(1983). | MR | Zbl

[Ta2] R. E. Tarjan: Applications of path compressions on balanced trees. J. Assoc. Comput. Math. 26(1979), 690–715. | MR

[Y] A. Yao: An $O(|E|\log \!\log |V|)$ algorithm for finding minimum spanning trees. Inform. Process. Lett. 4(1975), 21–23. | Zbl