A few remarks on the history of MST-problem

Jaroslav Nešetřil

Archivum Mathematicum (1997)

  • Volume: 033, Issue: 1-2, page 15-22
  • ISSN: 0044-8753

Abstract

top
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.

How to cite

top

Nešetřil, Jaroslav. "A few remarks on the history of MST-problem." Archivum Mathematicum 033.1-2 (1997): 15-22. <http://eudml.org/doc/248020>.

@article{Nešetřil1997,
abstract = {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.},
author = {Nešetřil, Jaroslav},
journal = {Archivum Mathematicum},
keywords = {minimum spanning tree},
language = {eng},
number = {1-2},
pages = {15-22},
publisher = {Department of Mathematics, Faculty of Science of Masaryk University, Brno},
title = {A few remarks on the history of MST-problem},
url = {http://eudml.org/doc/248020},
volume = {033},
year = {1997},
}

TY - JOUR
AU - Nešetřil, Jaroslav
TI - A few remarks on the history of MST-problem
JO - Archivum Mathematicum
PY - 1997
PB - Department of Mathematics, Faculty of Science of Masaryk University, Brno
VL - 033
IS - 1-2
SP - 15
EP - 22
AB - 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.
LA - eng
KW - minimum spanning tree
UR - http://eudml.org/doc/248020
ER -

References

top
  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 ( | E | log log | V | ) algorithm for finding minimum spanning trees, Inform. Process. Lett. 4(1975), 21–23. Zbl1220.81184

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.