Algorithms and Data Structures for Dynamic Graph Problems (thesis)
Report ID: TR-229-89Author: Westbrook, Jeffrey
Date: 1989-10-00
Pages: 92
Download Formats: |PDF|
Abstract:
We give data structures, algorithms, and lower bounds for three problems on dynamic graph, i.e., graphs that are being modified on-line. We consider the problem of maintaining the connected components of a graph undergoing edge insertions and backtracking edge deletions. We analyze several algorithms for the set union with backtracking problem, a variant of the classical disjoint set union (equivalence) problem in which an extra operation, de-union undoes the most recently performed union operation not yet undone. The most efficient such algorithms have an amortized running time of O(log n/ log log n) per operation, where n is the total number of elements in all the sets. We prove that any separable pointer-based algorithm for the problem requires omega(log n/ log log n) time per operation, thus showing that our upper bound an amortized time is tight. We use these fast algorithms to build an algorithm with the same resource bounds that maintains the connected components of an undirected graph undergoing edge insertion and backtracking edge deletion. By a simple reduction, the lower bounds for set union with backtracking can be applied to the connected components problem. We examine the twin problems of maintaining the bridge-connected components or the biconnected components of a graph being changed by vertex and edge insertions. We give a basic algorithm that is suitable for both problems. With simple data structures, this algorithm runs in O(n log n + m) time, where n is the number of vertices and m is the number of operations. We develop a modified version of the dynamic trees of Sleator and Tarjan that is suitable for efficient recursive algorithms, and use it to reduce the running time of the algorithms for both problems to O(m alpha(m,n)), where alpha is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms use O(n) space. We investigate the problem of maintaining a minimum spanning forest and the connected components of an embedded, edge-weighted planar graph undergoing changes in edge weight as well as edge and vertex insertion and deletion. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithms run in O(log n) amortized time per operation and O(n) space.