dyn.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Dynamic Spanning Trees}\id{dynchap}%
   6
   7 \section{Dynamic graph algorithms}
   8
   9 In many applications, we often need to solve a~certain graph problem for a~sequence
  10 of graphs that differ only a~little, so recomputing the solution from scratch for
  11 every graph would be a~waste of time. In such cases, we usually turn our attention
  12 to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure
  13 that remembers a~graph and offers operations that modify the structure of the graph
  14 (let's say by insertion and deletion of edges) and also operations that query the
  15 result of the problem for the current state of the graph.
  16 A~typical example of a~problem solved by such algorithms is dynamic maintenance of
  17 connected components:
  18
  19 \problemn{Dynamic connectivity}
  20 Maintain an~undirected graph under a~sequence of the following operations:
  21 \itemize\ibull
  22 \:$\<Init>(n)$ --- create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$,\foot{%
  23 The structure could support dynamic addition and removal of vertices, too,
  24 but this is easy to add and infrequently used, so we will rather define
  25 the structure with a~fixed set of vertices for clarity.}
  26 \:$\<Insert>(G,u,v)$ --- insert an~edge $uv$ to~$G$ and return its unique
  27 identifier (assuming that the edge did not exist yet),
  28 \:$\<Delete>(G,e)$ --- delete an~edge specified by its identifier from~$G$,
  29 \:$\<Connected>(G,u,v)$ --- test if $u$ and~$v$ are in the same connected component of~$G$.
  30 \endlist
  31
  32 \para
  33 We have already encountered a~special case of dynamic connectivity when implementing the
  34 Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
  35 any edges from the graph, which makes the problem substantially easier. This special
  36 case is sometimes called an~\df{incremental} or \df{semidynamic} graph algorithm.
  37 We mentioned the Union-Find data structure of Tarjan and van Leeuwen that is able
  38
  39 time $\O(n+m\timesalpha(m,n))$
  40
  41
  42 %--------------------------------------------------------------------------------
  43
  44 \section{Sleator-Tarjan trees}
  45
  46
  47 \endpart