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