Lecture I - Minimum Spanning Trees
Dates
21.9. (revision of Kruskal's/Jarník's/Borůvka's algorithm, their combinations, contractions, and a linear algorithm for planar graphs)
5.10. (Fredman-Tarjan, Gabow et al., Karger-Klein-Tarjan [almost all])
13.10. (finished Karger-Klein-Tarjan, Edmond's algorithm for arborescences in digraphs)
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