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:





Test Solutions