A BRICS Mini-Course
May 29, June 2, 1995
University of Salerno
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.
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.
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.
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.