Dynamic connectivity

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 set V of vertices of the graph is fixed, but the set E of edges can change. The three cases, in order of difficulty, are: Edges are only added to the graph (this can be called incremental connectivity); Edges are only deleted from the graph (this can be called decremental connectivity); Edges can be either added or deleted (this can be called fully dynamic connectivity). 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. Each set represents a connected component; there is a path between x and y if and only if they belong to the same set. The amortized time per operation is , where n is the number of vertices and α is the inverse Ackermann function. The case in which edges can only be deleted was solved by Shimon Even and Yossi Shiloach. The structure uses a table that specifies, for each vertex, the name of the component to which it belongs. Thus a connectivity query takes constant time. The challenge is to update the table when an edge is deleted. When edge u-v is deleted in a forest, the tree containing that edge is broken to two trees: one of them contains u and the other contains v. The table is updated in the following way. Scan the tree starting from u (using any tree scan algorithm, such as DFS). Scan the tree starting from v. Do the above two procedures in parallel, i.e., either using two parallel processes, or by interleaving their steps (make a step of first scan, then a step of the second scan, then a step of the first scan, etc.). Suppose the first scan that terminates is the scan from u (so we know that the tree containing u is the smaller one).