ANALYSIS OF ALGORITHMS (0368.4222.01)

Spring 2007, Tel Aviv University

Lecturer: Uri Zwick

Mailing List: http://listserv.tau.ac.il/archives/cs0368-4222-01.html

List of subjects:

Minimum Spanning Trees

· Basic properties: the blue and red rules

· Classical algorithms: Boruvka, Kruskal, Prim

· The linear time verification algorithm of Komlos (and King)

· The randomized linear time algorithm of Karger, Klein and Tarjan

Link to King's paper
Link to the Karger-Klein-Tarjan paper
Motwani & Raghavan: Randomized Algorithms, pages 296-302.

Problem Set no. 1

Global minimum cuts

· The deterministic algorithm of Stoer and Wagner

· The randomized algorithm of Karger and Stein

Link to the Stoer-Wagner paper
Link to the Karger-Stein paper

Motwani & Raghavan: Randomized Algorithms, pages 289-295.

Shortest paths algorithms

· Goldberg's scalling algorithm

Lecture notes

Problem Set no. 2

Minimum cost flow and weighted bipartite matching

· The cycle canceling algorithm

· The successive cheapest augmenting path algorithm

· Weighted bipartite matching – the assignment problem

· The minimum mean cost cycle canceling algorithm of Goldberg and Tarjan

Lecture notes
Ahuja, Magnanti, Orlin: Network flows, Chapters 9, 10.

Problem Set no. 3

Non-bipartite matching

· Augmenting paths and Hungarian trees

· The minimum vertex cover in bipartite graphs

· The blossom shrinking algorithm of Edmonds

· The odd vertex cover problem

Lecture notes
Mehlhorn & Naher: LEDA – A platform for combinatorial and geometric computing, pages 393-413.
Ahuja, Magnanti, Orlin: Network flows, Chapter 12.