From 37cdb2669cbcd35c2c4e25eba048849d775bf49b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 7 Apr 2008 18:56:16 +0200 Subject: [PATCH] Introduction to dynamic algorithms. --- Makefile | 2 +- dyn.tex | 45 +++++++++++++++++++++++++++++++++++++++++++++ mst.tex | 3 ++- saga.tex | 1 + 4 files changed, 49 insertions(+), 2 deletions(-) create mode 100644 dyn.tex diff --git a/Makefile b/Makefile index 13a9679..a6eb559 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ all: saga.ps -CHAPTERS=cover mst ram adv opt rank notation +CHAPTERS=cover mst ram adv opt dyn rank notation %.dvi: %.tex macros.tex biblio.bib tex $< && bibtex $* && tex $< && tex $< diff --git a/dyn.tex b/dyn.tex new file mode 100644 index 0000000..b16f43a --- /dev/null +++ b/dyn.tex @@ -0,0 +1,45 @@ +\ifx\endpart\undefined +\input macros.tex +\fi + +\chapter{Dynamic Spanning Trees}\id{dynchap}% + +\section{Dynamic graph algorithms} + +In many applications, we often need to solve a~certain graph problem for a~sequence +of graphs that differ only a~little, so recomputing the solution from scratch for +every graph would be a~waste of time. In such cases, we usually turn our attention +to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure +that remembers a~graph and offers operations that modify the structure of the graph +(let's say by insertion and deletion of edges) and also operations that query the +result of the problem for the current state of the graph. +A~typical example of a~problem solved by such algorithms is dynamic maintenance of +connected components: + +\problemn{Dynamic connectivity} +Maintain an~undirected graph under a~sequence of the following operations: +\itemize\ibull +\:$\(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.} +\:$\(G,u,v)$ --- insert an~edge $uv$ to~$G$ and return its unique +identifier (assuming that the edge did not exist yet), +\:$\(G,e)$ --- delete an~edge specified by its identifier from~$G$, +\:$\(G,u,v)$ --- test if $u$ and~$v$ are in the same connected component of~$G$. +\endlist + +\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 .... + + +%-------------------------------------------------------------------------------- + +\section{Sleator-Tarjan trees} + + +\endpart diff --git a/mst.tex b/mst.tex index 00d818f..f054c1e 100644 --- a/mst.tex +++ b/mst.tex @@ -317,7 +317,7 @@ Theorem \ref{mstthm}), so it is the heaviest edge on the cycle $T_{min}[e]+e$. %-------------------------------------------------------------------------------- -\section{Classical algorithms} +\section{Classical algorithms}\id{classalg}% The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm. For each of them, we first show the general version of the algorithm, then we prove that @@ -466,6 +466,7 @@ can be maintained in $\O(\alpha(n))$ time amortized per operation. \proof Proven by Tarjan and van Leeuwen in \cite{tarjan:setunion}. +See Chapter~\ref{dynchap} for more context. \qed \FIXME{Define Ackermann's function. Use $\alpha(m,n)$?} diff --git a/saga.tex b/saga.tex index 42243a8..6fbc7fc 100644 --- a/saga.tex +++ b/saga.tex @@ -6,6 +6,7 @@ \input ram.tex \input adv.tex \input opt.tex +\input dyn.tex \input rank.tex \input notation.tex -- 2.39.5