Dates

19. 9. The classic algorithms: Kruskal, Jarník, Borůvka
26.9. The advanced algorithms: Ford-Fulkerson, Gabow et al.
4.10. Randomized algorithm of Karger-Klein-Tarjan; Arborescences and Edmond's algorithm

Reading

J. Eisner: State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion (1997) [PDF]

Marvelous survey of algorithms which appeared before 1997. See chapters 3 (Kruskal, Jarník), 4 (Borůvka and contractions), 5 (Fredman-Tarjan; Gabow et al.) and 7 (Karger-Klein-Tarjan)

H. Gabow, Z. Galil, T. Spencer, R. Tarjan (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica 6 (2): 109. doi:10.1007/bf02579168

Very clear presentation of the algorithm of Gabow et al.

T. Chan: Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees (1998)  doi:10.1016/S0020-0190(98)00129-X

The simple proof of the sampling lemma used in Karger-Klein-Tarjan.

J. Kleinberg, E. Tardos: Algorithm Design [Section 4.9] [PDF]

Read this for the Edmonds' branching algorithm for min-cost arborescences.

Historical references

• R. Graham, P. Hell (1985). "On the history of the minimum spanning tree problem", Annals of the History of Computing 7 (1): 43–57,doi:10.1109/MAHC.1985.10011
• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nešetřilová. 
• M. Fredman, R. Tarjan (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM 34 (3): 596.doi:10.1145/28869.28874.
• H. Gabow, Z. Galil, T. Spencer, R. Tarjan (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica 6 (2): 109. doi:10.1007/bf02579168
• R. Karger, P. Klein, R. Tarjan (1995). "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery 42 (2): 321–328, doi:10.1145/201019.201022
• Chu, Y. J.; Liu, T. H. (1965), "On the Shortest Arborescence of a Directed Graph", Science Sinica 14: 1396–1400
• Edmonds, J. (1967), "Optimum Branchings", J. Res. Nat. Bur. Standards 71B: 233–240, doi:10.6028/jres.071b.032

Slides