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.
@article{107593,
author = {Jaroslav Ne\v set\v ril},
title = {A few remarks on the history of MST-problem},
journal = {Archivum Mathematicum},
volume = {033},
year = {1997},
pages = {15-22},
zbl = {0909.05022},
mrnumber = {1464297},
language = {en},
url = {http://dml.mathdoc.fr/item/107593}
}
Nešetřil, Jaroslav. A few remarks on the history of MST-problem. Archivum Mathematicum, Tome 033 (1997) pp. 15-22. http://gdmltest.u-ga.fr/item/107593/
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.
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.
K jednomu minimálnímu problému O. Borůvky, Čas. pro pěst. mat. 85(1960), 93–94.
Kombinatorická analýza v praxi, SNTL, Prague, 1967.
A linear-work parallel algorithm for finding minimum spanning trees, Proc. of SPAA, 1994.
Discrete variable extremum problems, Oper. Research 5(1957). | MR 0089098
Some theorems on spanning subtrees of a graph, Indag. Math. XXII, 2(1960), 196–199. | MR 0109795 | Zbl 0094.17604
Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM J. of Computing 21, 6(1992), 1184–1192. | MR 1192301
Optimum branchings, J. Res. Nat. Bur. Standards 71B(1967), 233–240. | MR 0227047 | Zbl 0198.52605
Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Proc. 31st Annual IEEE Symp. on Found. of Comp. Sci., 1966, 719–725.
Fibonacci heaps and their uses in network optimization algorithms, Proc. 25th Annual IEEE Symp. on Found. of Comp. Sci., 1984, 338–346.
Efficient implementation of graph algorithms using contraction, Proc. 25th Annual IEEE Symp. on Foundations of Computer Sci., 1984, 347–357.
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica 6(1986), 109–122. | MR 0875837
On the history of the minimum spanning tree problem, Annals of the History of Computing 7(1985), 43–57. | MR 0783327
O jistém problému minimálním, Práce mor. přírodověd. spol. v Brně VI, 4(1930), 57–63.
O minimálních grafech obsahujících $n$ daných bodů, Čas. pro pěst. mat. 63(1934), 223–235.
On some communication network problem, Proc. Symp. Applied Math. (1960), 261–280. | MR 0122573
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 1328413
A randomized linear-time algorithm to find minimum spanning trees, J. Assoc. Comp. Mach. 42(1995), 321–328. | MR 1409738
A simpler minimum spanning tree verification algorithm, manuscript 1993. | Zbl 0868.68061
A randomized linear-time algorithm for finding minimum spanning trees, Proc. 26th Annual ACM Symp. on theory of Computing, 1994, 9–15.
Linear verification for spanning trees, Combinatorica 5(1985), 57–65. | MR 0803240 | Zbl 0579.05031
Greedoids, Springer Verlag (1991). | MR 1183735
Vojtěch Jarník’s work in combinatorial optimization, KAM Series No. 96–315.
Súvislé grafy s minimálnou hodnotou v konečnom súvislom grafe, Čas pro pěst. mat. (1961), 1–6. | MR 0143197
On the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7(1956), 48–50. | MR 0078686
Sur la liaison et la division des points d’un ensemble fini, Colloq. Math. 2(1949-1951), 282–285. | MR 0048832
Prohledávání, třídění a optimalizace stromů, doctoral dissertation, Prague, 1997.
The shortest connecting network and some generalisations, Bell. Syst. Tech. J. 36(1957), 1389–1401.
A comprehensive program for network problems, Computer J. 3(1960), 89–97. | MR 0129484
Data structures and network algorithms, CBMS-NSF Regional Conf. Series in Applied Math., SIAM 44(1983). | MR 0826534 | Zbl 0584.68077
Applications of path compressions on balanced trees, J. Assoc. Comput. Math. 26(1979), 690–715. | MR 0545544
An $O(|E|\log \!\log |V|)$ algorithm for finding minimum spanning trees, Inform. Process. Lett. 4(1975), 21–23. | Zbl 1220.81184