| Title:
|
A few remarks on the history of MST-problem (English) |
| Author:
|
Nešetřil, Jaroslav |
| Language:
|
English |
| Journal:
|
Archivum Mathematicum |
| ISSN:
|
0044-8753 (print) |
| ISSN:
|
1212-5059 (online) |
| Volume:
|
33 |
| Issue:
|
1 |
| Year:
|
1997 |
| Pages:
|
15-22 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| MSC:
|
01-01 |
| MSC:
|
01A60 |
| MSC:
|
01A70 |
| MSC:
|
05C05 |
| idZBL:
|
Zbl 0909.05022 |
| idMR:
|
MR1464297 |
| . |
| Date available:
|
2008-06-06T21:32:06Z |
| Last updated:
|
2012-05-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/107593 |
| . |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[C] K. Čulík: K jednomu minimálnímu problému O. Borůvky.Čas. pro pěst. mat. 85(1960), 93–94. |
| Reference:
|
[CDF] K. Čulík, V. Doležal, M. Fiedler: Kombinatorická analýza v praxi.SNTL, Prague, 1967. |
| Reference:
|
[CKT] R. Cole, P. N. Klein, R. E. Tarjan: A linear-work parallel algorithm for finding minimum spanning trees.Proc. of SPAA, 1994. |
| Reference:
|
[Da] G. Dantzig: Discrete variable extremum problems.Oper. Research 5(1957). MR 0089098 |
| Reference:
|
[Di] E. W. Dijkstra: Some theorems on spanning subtrees of a graph.Indag. Math. XXII, 2(1960), 196–199. Zbl 0094.17604, MR 0109795 |
| Reference:
|
[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 |
| Reference:
|
[E] J. Edmonds: Optimum branchings.J. Res. Nat. Bur. Standards 71B(1967), 233–240. Zbl 0198.52605, MR 0227047 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[K] R. Kalaba: On some communication network problem.Proc. Symp. Applied Math. (1960), 261–280. MR 0122573 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[Ki] V. King: A simpler minimum spanning tree verification algorithm.manuscript 1993. Zbl 0868.68061 |
| Reference:
|
[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. |
| Reference:
|
[Ko] J. Komlos: Linear verification for spanning trees.Combinatorica 5(1985), 57–65. Zbl 0579.05031, MR 0803240 |
| Reference:
|
[KLS] B. Korte, L. Lovasz, R. Schrader: Greedoids.Springer Verlag (1991). MR 1183735 |
| Reference:
|
[KN] B. Korte, J. Nešetřil: Vojtěch Jarník’s work in combinatorial optimization.KAM Series No. 96–315. |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[M] E. Milková: Prohledávání, třídění a optimalizace stromů.doctoral dissertation, Prague, 1997. |
| Reference:
|
[Pr] R. C. Prim: The shortest connecting network and some generalisations.Bell. Syst. Tech. J. 36(1957), 1389–1401. |
| Reference:
|
[So] E. W. Solomon: A comprehensive program for network problems.Computer J. 3(1960), 89–97. MR 0129484 |
| Reference:
|
[Ta1] R. E. Tarjan: Data structures and network algorithms.CBMS-NSF Regional Conf. Series in Applied Math., SIAM 44(1983). Zbl 0584.68077, MR 0826534 |
| Reference:
|
[Ta2] R. E. Tarjan: Applications of path compressions on balanced trees.J. Assoc. Comput. Math. 26(1979), 690–715. MR 0545544 |
| Reference:
|
[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 |
| . |
