In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.
The three cases, in order of difficulty, are: After each addition/deletion of an edge, the dynamic connectivity structure should adapt itself such that it can give quick answers to queries of the form "is there a path between x and y?"
(equivalently: "do vertices x and y belong to the same connected component?").
If edges can only be added, then the dynamic connectivity problem can be solved by a disjoint-set data structure.
, where n is the number of vertices and α is the inverse Ackermann function.
[1][2] The case in which edges can only be deleted was solved by Shimon Even and Yossi Shiloach.
[3] The structure uses a table that specifies, for each vertex, the name of the component to which it belongs.
Since we always rename the smaller sub-component, the amortized time for a delete operation is
So for each vertex v, we maintain three sets of edges (backward, local and forward).
While Q is not empty: If the edge deletion does not break any component and we are in case 2.2, then eventually the procedure will halt.
In this case it is easy to see that the BFS structure is maintained correctly.
In this case all the changes made in the BFS structure are ignored, and we go back to the BFS structure we had just before the deletion, except that the deleted edge is now replaced by an artificial edge.
[4] whenever an edge is processed in the procedure, one of its endpoints drops by one level.
Since the lowest level a vertex can reach in runs which are terminated by process B is
The challenge is to quickly find such a replacement edge, if it exists.
Let L=lg n. The level of each edge inserted to the graph is initialized to L, and may decrease towards 0 during delete operations.
[5][6] The Query and Insert operations use only the largest forest FL.
When such an edge e = x−y is deleted, it is first removed from FL and from all smaller spanning forests to which it belongs, i.e. from every Fi with i ≥ level(e).
Start with the smallest spanning forest which contained e, namely, Fi with i = level(e).
Suppose wlog that Tx is the smaller tree (i.e. contains at most half the nodes of T; we can tell the size of each subtree by an annotation added to the Euler trees).
Given a graph G(V,E) and a subset T⊆V, define cutset(T) as the set of edges that connect T with V\T.
The cutset structure is a data structure that, without keeping the entire graph in memory, can quickly find an edge in the cutset, if such an edge exists.
Suppose there are n vertices; then each vertex can be represented by a number with lg(n) bits.
If in the first level xor(T) returns an illegal value, meaning that cutset(T) has two or more edges, then there is a chance that in the next level, which contains fewer edges, xor(T) will return a legal value since cutset(T) will contain a single edge.
If xor(T) still returns an illegal value, continue to the next level, etc.
Since the number of edges is decreasing, there are two cases: It is possible to prove that the probability of success is at least 1/9.
Next, create a collection of C lg(n) independent versions of the level structure, where C is a constant.
The Insert and Delete operations on the cutset structure are done in exactly the same way: the edge inserted/deleted is XORed into both its endpoints.
When an edge is deleted from the spanning forest used for the dynamic connectivity structure, the cutset structure is used to find a replacement edge.
This makes the delete operation trivial: we simply need to split the tree into its two parts if the edge to delete is part of our forest, or ignore the operation otherwise.