\problemn{Dynamic connectivity}
Maintain an~undirected graph under a~sequence of the following operations:
\itemize\ibull
-\:$\<Init>(n)$ --- create a~graph with $n$~isolated vertices,\foot{%
-The structure could support dynamic additional and removal of vertices, too,
-but this is easy to add and infrequently used, so we will rather use a~fixed
-set of vertices for clarity.}
+\:$\<Init>(n)$ --- create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$,\foot{%
+The structure could support dynamic addition and removal of vertices, too,
+but this is easy to add and infrequently used, so we will rather define
+the structure with a~fixed set of vertices for clarity.}
\:$\<Insert>(G,u,v)$ --- insert an~edge $uv$ to~$G$ and return its unique
identifier (assuming that the edge did not exist yet),
\:$\<Delete>(G,e)$ --- delete an~edge specified by its identifier from~$G$,
\para
We have already encountered a~special case of dynamic connectivity when implementing the
Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
-any edges from the graph (this is sometimes called a~\df{semidynamic graph algorithm}),
-which makes the problem substantially easier. We mentioned the Union-Find data structure
-of Tarjan and van Leeuwen ....
+any edges from the graph, which makes the problem substantially easier. This special
+case is sometimes called an~\df{incremental} or \df{semidynamic} graph algorithm.
+We mentioned the Union-Find data structure of Tarjan and van Leeuwen \cite{tarjan:setunion}
+which can be used for that: queries on connectedness translate to \<Find>, edge
+insertions to \<Find> followed by \<Union> if the edge connects two different
+components. This way, a~sequence of $m$~operations starting with an~empty graph
+on $n$~vertices is processed in time $\O(m\timesalpha(m,n))$ and this works even
+on the Pointer Machine. Fredman and Saks \cite{fredman:cellprobe} have proven
+a~matching lower bound in the cell-probe model which is stronger than RAM with
+$\O(\log n)$-bit words.
+
+The edges that have triggered the \<Union>s form a~spanning forest of the current graph.
+So far, all known algorithms for dynamic connectivity maintain some sort of a~spanning
+tree. This suggests that a~dynamic MST algorithm could be obtained by modifying the
+dynamic connectivity algorithms. This will indeed turn out to be true. Semidynamic MST
+is easy to achieve before the end of this section, but making it fully dynamic will require
+more effort, so we will review some of the existing data structures in the meantime.
+
+We however have to answer one important question first: What should be the output of
+our MSF data structure? Adding an~operation that would return the MSF of the current
+graph is of course possible, but somewhat impractical as this operation has to
+spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
+be to make the \<Insert> and \<Delete> operations report the list of modifications
+of the MSF caused by the change in the graph.
+
+Let us see what happens when we \<Insert> an~edge~$e$ to a~graph~$G$ with a~minimum spanning
+forest~$F$, obtaining a~new graph~$G'$ with its MSF~$F'$. If $e$~connects two components of~$G$ (and
+therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the following cases happens:
+Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
+and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
+
+Correctness of the former case follows immediately from the Theorem on Minimality by order
+(\ref{mstthm}), because all $F'$-light would be also $F$-light, which is impossible as $F$~was
+minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
+on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
+(\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$
+of~$F$ containing both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
+apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest edge of the cut~$\delta_G(T_1)$
+and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
+
+A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
+an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
+the new components. If there is no such replacement edge, we have deleted a~bridge,
+so the MSF has to remain disconnected.
+
+The idea of reporting differences in the MSF indeed works very well. We can summarize
+what we have shown by the following lemma:
+
+\lemma
+An~\<Insert> or \<Delete> of an~edge in~$G$ causes at most one edge addition, edge
+removal or edge exchange in $\msf(G)$.
+
+\paran{Semidynamic MSF}%
+To obtain a~semidynamic MSF algorithm, we need to keep the forest in a~data structure which
+supports search for the heaviest edge on the path connecting a~given pair
+of vertices. This can be handled efficiently by the Link-Cut trees of Sleator and Tarjan:
+
+\thmn{Link-Cut Trees, Sleator and Tarjan \cite{sleator:trees}}
+There is a~data structure that represents a~forest of rooted trees on~$n$ vertices.
+Each edge of the forest has a~weight drawn from a~totally ordered set. The structure
+supports the following operations in time $\O(\log n)$ amortized:
+
+XXX
+
+\proof
+See \cite{sleator:trees}.
+\qed
+
%--------------------------------------------------------------------------------
-\section{Sleator-Tarjan trees}
+\section{ET trees}
\endpart
projects / saga.git / blobdiff