A few remarks on the history of MST-problem

 Access to full text

 Full (PDF)

1. 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. 
2. 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. 
3. K jednomu minimálnímu problému O. Borůvky, Čas. pro pěst. mat. 85(1960), 93–94. 
4. Kombinatorická analýza v praxi, SNTL, Prague, 1967. 
5. A linear-work parallel algorithm for finding minimum spanning trees, Proc. of SPAA, 1994. 
6. Discrete variable extremum problems, Oper. Research 5(1957). MR0089098
7. Some theorems on spanning subtrees of a graph, Indag. Math. XXII, 2(1960), 196–199. Zbl0094.17604MR0109795
8. Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM J. of Computing 21, 6(1992), 1184–1192. MR1192301
9. Optimum branchings, J. Res. Nat. Bur. Standards 71B(1967), 233–240. Zbl0198.52605MR0227047
10. Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Proc. 31st Annual IEEE Symp. on Found. of Comp. Sci., 1966, 719–725. 
11. Fibonacci heaps and their uses in network optimization algorithms, Proc. 25th Annual IEEE Symp. on Found. of Comp. Sci., 1984, 338–346. 
12. Efficient implementation of graph algorithms using contraction, Proc. 25th Annual IEEE Symp. on Foundations of Computer Sci., 1984, 347–357. 
13. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica 6(1986), 109–122. MR0875837
14. On the history of the minimum spanning tree problem, Annals of the History of Computing 7(1985), 43–57. MR0783327
15. O jistém problému minimálním, Práce mor. přírodověd. spol. v Brně VI, 4(1930), 57–63. 
16. O minimálních grafech obsahujících $n$ daných bodů, Čas. pro pěst. mat. 63(1934), 223–235. 
17. On some communication network problem, Proc. Symp. Applied Math. (1960), 261–280. MR0122573
18. 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. MR1328413
19. A randomized linear-time algorithm to find minimum spanning trees, J. Assoc. Comp. Mach. 42(1995), 321–328. MR1409738
20. A simpler minimum spanning tree verification algorithm, manuscript 1993. Zbl0868.68061
21. A randomized linear-time algorithm for finding minimum spanning trees, Proc. 26th Annual ACM Symp. on theory of Computing, 1994, 9–15. 
22. Linear verification for spanning trees, Combinatorica 5(1985), 57–65. Zbl0579.05031MR0803240
23. Greedoids, Springer Verlag (1991). MR1183735
24. Vojtěch Jarník’s work in combinatorial optimization, KAM Series No. 96–315. 
25. Súvislé grafy s minimálnou hodnotou v konečnom súvislom grafe, Čas pro pěst. mat. (1961), 1–6. MR0143197
26. On the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7(1956), 48–50. MR0078686
27. Sur la liaison et la division des points d’un ensemble fini, Colloq. Math. 2(1949-1951), 282–285. MR0048832
28. Prohledávání, třídění a optimalizace stromů, doctoral dissertation, Prague, 1997. 
29. The shortest connecting network and some generalisations, Bell. Syst. Tech. J. 36(1957), 1389–1401. 
30. A comprehensive program for network problems, Computer J. 3(1960), 89–97. MR0129484
31. Data structures and network algorithms, CBMS-NSF Regional Conf. Series in Applied Math., SIAM 44(1983). Zbl0584.68077MR0826534
32. Applications of path compressions on balanced trees, J. Assoc. Comput. Math. 26(1979), 690–715. MR0545544
33. An $O\left(\right|E|loglog|V\left|\right)$ algorithm for finding minimum spanning trees, Inform. Process. Lett. 4(1975), 21–23. Zbl1220.81184

1. Martin Mareš, Two linear time algorithms for MST on minor closed graph classes
2. Eva Milková, Moderní pohled na „jistý problém minimální‟
3. Pavel Šišma, Vznik a vývoj teorie grafů