Giuseppe F. Italiano, University of Rome II, Tor Vergata, Italy

Dynamic Graph Algorithms
In many applications of graph algorithms, including communication networks, graphics, assembly planning, and VLSI design, graphs are subject to discrete changes, such as additions or deletions of edges or vertices. In the last decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithms and data structures for dynamic graphs has been discovered. This talk is intended as an overview of this field.
In a typical dynamic graph problem one would like to answer queries on graphs that are undergoing a sequence of updates, for instance, insertions and deletions of edges and vertices. The goal of a dynamic graph algorithm is to update efficiently the solution of a problem after dynamic changes, rather than having to recompute it from scratch each time. Given their powerful versatility, it is not surprising that dynamic algorithms and dynamic data structures are often more difficult to design and analyze than their static counterparts.

References
C. Demetrescu and G. F. Italiano, A new approach to dynamic all pairs shortest paths, Journal of the ACM, 51(6):968--992, 2004.

C. Demetrescu and G. F. Italiano, Trade-offs for fully dynamic reachability on dags: Breaking through the ${O}(n^2)$ barrier, Journal of the ACM, 52(2):147--156, 2005.

D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig, Sparsification - A technique for speeding up dynamic graph algorithms, Journal of the ACM, vol. 44 (1997), 669--696.

D. Eppstein, Z. Galil, G. F. Italiano, and T. H. Spencer, Separator based sparsification I: planarity testing and minimum spanning trees, Journal of Computer and System Science, vol. 52, no. 1 (1996), 3-27.

D. Eppstein, Z. Galil, G. F. Italiano, T. H. Spencer, Separator based sparsification II: edge and vertex connectivity, SIAM Journal on Computing, vol. 28 (1999), 341--381.

G. N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and $k$ smallest spanning trees, SIAM J. Comput.ing, 26:484-538, 1997.

M.~L. Fredman and M.R. Henzinger, Lower bounds for fully dynamic connectivity problems in graphs, Algorithmica, 22(3): 351-362 (1998).

M. R. Henzinger and V. King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Journal of the ACM, 46(4):502--536, 1999.

M. R. Henzinger and V.~King, Fully dynamic biconnectivity and transitive closure, Proc. Proc. 36th IEEE Symp. Foundations of Computer Science, pages 664-672, 1995.

M. Henzinger and V. King, Maintaining minimum spanning forests in dynamic graphs, SIAM Journal on Computing, 31(2):364--374, 2001.

M.R. Henzinger and M. Thorup, Sampling to provide or to bound: With applications to fully dynamic graph algorithms, Random Struct. Algorithms, 11(4): 369-379 (1997).

J. Holm, K. de~Lichtenberg, and M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM, 48:723--760, 2001.

J. Holm, K. de Lichtenberg and M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. {\sl J. Assoc. Comput. Mach.}, 48(4):723--760, 2001.

V. King and G. Sagert, A fully dynamic algorithm for maintaining the transitive closure, Journal of Computer and System Sciences, 65(1):150--167, 2002.

L. Roditty and U. Zwick, Improved dynamic reachability algorithms for directed graphs, Proceedings of 43thÊ Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 679--688, 2002.

L. Roditty and U. Zwick, A fully dynamic reachability algorithm for directed graphs with an almost linear update time, Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 184--191, 2004.

P. Sankowski, Dynamic transitive closure via dynamic matrix inverse, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), Rome, Italy, 2004.

M. Thorup, Fully-dynamic all-pairs shortest paths: Faster and allowing negative Cycles, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04), pages 384--396, 2004.

M. Thorup, Worst-case update times for fully-dynamic all-pairs shortest paths, Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), 2005.