The grade is composed of:
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
Shimon Even, Yossi Shiloach: An On-Line Edge-Deletion Problem
J. ACM 28(1):1-4 (1981)
Greg N. Frederickson: Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications.
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)
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: