Fully dynamic biconnectivity and transitive closure

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(pow2(log(n)) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(pow(log(n),4)). Only recently the best deterministic result for this problem was improved to Osqrt(n.pow2(log(n))). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let M be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(M.sqrt(n.pow2(log(n)))+n); or (2) query time O(n/logn) and update time O[pow(M,(u-1)/u))].pow2(log(n))=O[M.pow(n,0.58).pow2(log(n))], where u is the exponent for boolean matrix multiplication (currently u=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(n.pow2(log(n)))

Monika Henzinger

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log2 n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log4 n). Only recently the best deterministic result for this problem was improved to O(Vn log2 n). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/log n) and update time O(mVn log2 n+n); or (2) query time O(n/log n) and update time O[n.pow(m,(u-1)/u)].pow2(log(n)) = O[n.pow(m,0.58).pow2(log(n)], where u is the exponent for boolean matrix multiplication (currently u = 2.38). The deletions-only algorithm answers queries in time O(n/log n). Its amortized update time is O(n log2 n).

IEEE1995

Randomized fully dynamic graph algorithms with polylogarithmic time per operation

Monika Henzinger

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of 0(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (Throughout the paper the logarithms are base 2.) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem ("Does the removal of k given edges disconnect the graph?") the expected time for p updates is O(p.pow(log(n),3)) and the expected time for q queries is O(p_k.pow(log(n),3)). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(p_k.pow(log(n),3)). This implies an algorithm to maintain a 1 + e- approximation of the minimum spanning tree in expected time O((p.pow(log(n),3).log U)/e) for p updates, where the weights of the edges are between 1 and U.

1999

Fully dynamic cycle-equivalence in graphs

Monika Henzinger

Two edges e_1 and e_2 of an undirected graph are cycle-equivalent iff all cycles that contain e_1 also contain e_2, i.e., iff e_1 and e_2 are a cut-edge pair. The cycle-equivalence classes of the control-flow graph are used in optimizing compilers to speed up existing control-flow and data-flow algorithms. While the cycle-equivalence classes can be computed in linear time, we present the first fully dynamic algorithm for maintaining the cycle-equivalence relation. In an n-node graph our data structure executes an edge insertion or deletion in O(sqrt(n.log n)) time and answers the query whether two given edges are cycle-equivalent in O(pow2(log(n))) time. We also present an algorithm for plane graphs with O(log n) update and query time and for planar graphs with O(log n) insertion time and O(log2 n) query and deletion time. Additionally, we show a lower bound of Ω(log n/log log n) for the amortized time per operation for the dynamic cycle-equivalence problem in the cell probe model

1994