BRICS · Programme · References

Dynamic Graph Algorithms

A BRICS Mini-Course
May 29, June 2, 1995

Lectures by
Giuseppe Italiano
University of Salerno


Programme

Monday May 29, 1995, 09:30-11:15 in Auditorium D4

Lecture 1. Introduction and basic dynamic graph algorithms.

In compilers, data bases, and combinatorial optimization problems, graph properties like connected components, minimum spanning trees, etc etc need to be computed repeatedly on graphs that closely resemble each other. Efficient algorithms for these situations are called dynamic graph algorithms. These are algorithms that allow the input graph to be modified by insertions and deletions of edges and vertices.

We will describe one of the first techniques designed for dynamic graphs: clustering. It is due to Frederickson and was first presented in 1982. The idea below clustering is the following. Assume we are supposed to maintain a certain tree of a dynamic graph (i.e., a minimum spanning tree, a spanning tree, etc etc). Clustering keeps track of the edges that are not part of this tree, by grouping them according to which of certain subtrees they connect. If the clustering is applied recursively, the information about these non-tree edges can be maintained even more efficiently in a topology tree. A refinement of the clustering technique appears in the idea of ambivalent data structures, again due to Frederickson, in which edges can belong to multiple groups, only one of which is actually selected depending on the topology of the given spanning tree.

Monday May 29, 1995, 12:45-14:30 in Auditorium D4

Lecture 2. Sparsification.

We will describe another main technique for dynamic graph algorithms. It is called sparsification and was designed by Eppstein, Galil, Italiano and Nissenzweig. This is a divide-and-conquer technique that can be used to reduce the dependence on the number of edges in a graph, so that the time bounds for maintaining some property of the graph match the times for computing in sparse graphs. Sparsification can be applied orthogonally to other data structuring techniques, and we will see a number of situations in which both clustering and sparsification combine to produce an efficient dynamic graph algorithm.

Friday June 2, 1995, 09:30-11:15 in Auditorium D4

Lecture 3. Semi-dynamic graph algorithms.

We will describe algorithms that maintain graph properties under edge insertions only. We focus on algorithms for edge- and vertex-connectivity, as many researchers (Westbrook & Tarjan, Galil & Italiano, La Poutre', Kanevsky Tamassia & Di Battista, Dinitz) have thouroughly studied these problems.

All these algorithms follow a common approach. Namely, they try to exploit the structure of the connectivity cuts and store this information in a tree (or generalized tree). This tree is then dynamically maintained using the set union data structures of Tarjan and van Leeuwen or slight modifications of these data structures. The tree structure of the connectivity cuts is fairly complicated, however, and it requires sophisticated data structures and a quite delicate analysis.

Friday June 2, 1995, 12:15-14:00 in Auditorium D4

Lecture 4. Fully dynamic randomized connectivity.

We will present a very recent randomized algorithm for graph connectivity due to King & Rauch. It is a Las-Vegas randomized algorithm, and uses the power of random sampling to speed up the updates.

References

  1. Eppstein, D., Galil, Z. and Italiano, G. F., Dynamic Graph Algorithms. Chapters 2-4 from preliminary version.
  2. Frederickson, G. N., Data Structures for on-line Updating of Minimum Spanning Trees, with Applications.
  3. Eppstein, D., Galil, Z., Italiano, G. F. and Nissenzweig, A., Sparsification - A Technique for Speeding up Dynamic graph Algorithms.
  4. Henzinger, M. R. and King, V., Randomised Dynamic Graph Algorithms with Polylogarithmic Time per Operation.