ANALYSIS OF ALGORITHMS (0368.4222.01)
Spring
2009, Tel Aviv University
Lecturer: Uri
Zwick
Minimum Spanning Trees
Basic properties: the blue and red rules
Classical algorithms: Boruvka, Kruskal, Prim
The randomized linear time algorithm of Karger, Klein and Tarjan
The linear time verification algorithm of Komlos (and King)
Link to the Karger-Klein-Tarjan paper
Motwani & Raghavan: Randomized Algorithms, pages 296-302.
Minimum directed spanning trees
Edmonds' cycle shriking algorithm
Tarjan's implementation
Shortest paths with positive and negative edge weights
Goldberg's scalling algorithm
Dynamic All-Pairs Shortest Paths
The algorithm of Demetrescu and Italiano
Link to the Demetrescu-Italiano paper
Global minimum cuts
The randomized algorithms of Karger and Stein
Problem
Set 4
Link
to the Karger-Stein paper
Motwani & Raghavan: Randomized Algorithms, pages 289-295.