Dynamic Algorithm Course

 

The grade is composed of:

80% Exam

14% Exercises

1% Classes Notice, you must attend the lectures!

 

Problem set 1 is due at 29/11/09

Problem set 2 is due at 20/12/09

Dynamic connectivity and minimum spanning tree

 

Shimon Even, Yossi Shiloach: An On-Line Edge-Deletion Problem

J. ACM 28(1):1-4 (1981)

 

Problem Set 1

 

Greg N. Frederickson: Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications.

SIAM J. Comput. 14(4): 781-798 (1985)

 

Problem Set 2

 

David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig: Sparsification - a technique for speeding up dynamic graph algorithms.

J. ACM (JACM) 44(5):669-696 (1997)

 

Monika Rauch Henzinger, Valerie King: Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.

J. ACM 46(4): 502-516 (1999)

 

Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.

J. ACM 48(4): 723-760 (2001)

 

Christian's talk

 

Dynamic reachability and strongly connected components

 

Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed

Acyclic Graphs. Inf. Process. Lett. 28(1): 5-11 (1988)

 

Liam Roditty, Uri Zwick: A fully dynamic reachability algorithm

for directed graphs with an almost linear update time. STOC 2004:

184-191

 

Slides

 

Test Solutions