From afdb04367d41d1b54ad3415777af885a9bab40e7 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 8 Apr 2008 23:06:53 +0200 Subject: [PATCH] Continuing with the intro to dynamic algorithms. --- PLAN | 1 + biblio.bib | 13 ++++++++++ dyn.tex | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 80 insertions(+), 3 deletions(-) diff --git a/PLAN b/PLAN index 8fc44e1..837118b 100644 --- a/PLAN +++ b/PLAN @@ -65,6 +65,7 @@ Spanning trees: - random sampling (propp:randommst) - mention bugs in Valeria's verification paper - more references on decision trees +- rename theorem on Minimality by order Models: diff --git a/biblio.bib b/biblio.bib index d0b9784..2c1aedd 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1283,3 +1283,16 @@ pages={2}, year={2002} } + +@inproceedings{ fredman:cellprobe, + author = {M. Fredman and M. Saks}, + title = {The cell probe complexity of dynamic data structures}, + booktitle = {STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing}, + year = {1989}, + isbn = {0-89791-307-8}, + pages = {345--354}, + location = {Seattle, Washington, United States}, + doi = {http://doi.acm.org/10.1145/73007.73040}, + publisher = {ACM}, + address = {New York, NY, USA}, +} diff --git a/dyn.tex b/dyn.tex index e8ecc4e..ea51c44 100644 --- a/dyn.tex +++ b/dyn.tex @@ -34,14 +34,77 @@ We have already encountered a~special case of dynamic connectivity when implemen Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete 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 that is able +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 \, edge +insertions to \ followed by \ 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 \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 \ and \ operations report the list of modifications +of the MSF caused by the change in the graph. + +Let us see what happens when we \ 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~\ 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~\ or \ 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 -time $\O(n+m\timesalpha(m,n))$ %-------------------------------------------------------------------------------- -\section{Sleator-Tarjan trees} +\section{ET trees} \endpart -- 2.39.2