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(n2) 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/