17^th Estonian Winter School in Computer Science (EWSCS)
XVII Eesti Arvutiteaduse Talvekool

Giuseppe Italiano

Dip. di Informatica, Sistemi e Produzione
Università di Roma "Tor Vergata"
Italy

Dynamic graph algorithms

Abstract

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. 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.

Course materials

• G. F. Italiano. Dynamic graph algorithms. Slides for EWSCS '12, 2012. [pdf]
• G. F. Italiano. Biconnectivity in directed graphs. Slides, 2012. [pdf]
• C. Demetrescu, D. Eppstein, Z. Galil, G. F. Italiano. Dynamic graph algorithms. In M. J. Atallah, ed., Algorithms and Theory of Computation Handbook, ch. 8. CRC Press, 1999. (Also in M. J. Atallah, M. Blanton, eds., Algorithms and Theory of Computation Handbook, 2nd ed., v. 1, ch. 9. CRC Press, 2009.)
• V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proc. of 40th Ann. Symp. on Foundations of Computer Science, FOCS '99 (New York, NY, Oct. 1999), pp. 81-91. IEEE Comput. Soc. Press, 1999.
  [doi: 10.1109/sffcs.1999.814580]
• J. Holm, K. de Lichtenberg, M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. of ACM, v. 48, n. 4, pp. 723-760, 2001.
  [doi: 10.1145/502090.502095]
• C. Demetrescu, G. F. Italiano. A new approach to dynamic all pairs shortest paths. J. of ACM, v. 51, n. 6, pp. 968-992, 2004.
  [doi: 10.1145/1039488.1039492]
• C. Demetrescu, G. F. Italiano. Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n²) barrier. J. of ACM, v. 52, n. 2, pp. 147-156, 2005.
  [doi: 10.1145/1059513.1059514]
• C. Demetrescu, G. F. Italiano. Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. on Algorithms, v. 2, n. 4, pp. 578-601, 2006.
  [doi: 10.1145/1198513.1198519]

Last changed March 3, 2012 21:54 EET by local organizers, ewscs12(at)cs.ioc.ee
EWSCS'12 page: //cs.ioc.ee/ewscs/2012/