Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Summary:
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.
References:
[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 0089098
[Di] E. W. Dijkstra: Some theorems on spanning subtrees of a graph. Indag. Math. XXII, 2(1960), 196–199. MR 0109795 | Zbl 0094.17604
[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 1192301
[E] J. Edmonds: Optimum branchings. J. Res. Nat. Bur. Standards 71B(1967), 233–240. MR 0227047 | Zbl 0198.52605
[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 0875837
[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 0783327
[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 0122573
[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 1328413
[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 1409738
[Ki] V. King: A simpler minimum spanning tree verification algorithm. manuscript 1993. Zbl 0868.68061
[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 0803240 | Zbl 0579.05031
[KLS] B. Korte, L. Lovasz, R. Schrader: Greedoids. Springer Verlag (1991). MR 1183735
[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 0143197
[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 0078686
[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 0048832
[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 0129484
[Ta1] R. E. Tarjan: Data structures and network algorithms. CBMS-NSF Regional Conf. Series in Applied Math., SIAM 44(1983). MR 0826534 | Zbl 0584.68077
[Ta2] R. E. Tarjan: Applications of path compressions on balanced trees. J. Assoc. Comput. Math. 26(1979), 690–715. MR 0545544
[Y] A. Yao: An $O(|E|\log \!\log |V|)$ algorithm for finding minimum spanning trees. Inform. Process. Lett. 4(1975), 21–23. Zbl 1220.81184
Search
Partner of
