rediscovered several times.
Recently, several significantly faster algorithms were discovered, most notably the
-$\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
+$\O(m\timesbeta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
and Pettie \cite{pettie:ackermann}.
This chapter attempts to survery the important algorithms for finding the MST and it
also presents several new ones.
-\section{Basic Properties}
+%--------------------------------------------------------------------------------
+
+\section{Basic properties}
In this section, we will examine the basic properties of spanning trees and prove
several important theorems to base the algorithms upon. We will follow the theory
is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
\qed
-\section{The Red-Blue Meta-Algorithm}
+%--------------------------------------------------------------------------------
+
+\section{The Red-Blue meta-algorithm}
Most MST algorithms can be described as special cases of the following procedure
(again following \cite{tarjan:dsna}):
When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
\proof
-Again by contradiction. Assume that $e$ is an edge painted red as the heaviest edge
+Again by contradiction. Suppose that $e$ is an edge painted red as the heaviest edge
of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
\qed
+%--------------------------------------------------------------------------------
+
\section{Classical algorithms}
The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.
produce a cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
loss of generality we can assume that $C=T_1[u_1v_1]\,v_1u_2\,T_2[u_2v_2]\,v_2u_3\,T_3[u_3v_3]\, \ldots \,T_k[u_kv_k]\,v_ku_1$.
Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
-or $v_{i-1}u_i$ (indexing cyclically). Assume that $e_1=v_1u_2$ (otherwise we reverse the orientation
+or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation
of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and we can continue in the same way,
getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction.
(Note that distinctness of edge weights was crucial here.)
Follows from the previous lemmata.
\qed
-\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}
+\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}%
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=$ a single-vertex tree containing an~arbitrary vertex of~$G$.
Follows from the above analysis.
\qed
-\section{Contractive algorithms}
+%--------------------------------------------------------------------------------
+
+\section{Contractive algorithms}\id{contalg}%
While the classical algorithms are based on growing suitable trees, they
can be also reformulated in terms of edge contraction. Instead of keeping
\rem
There are several other possibilities how to find the MST of a planar graph in linear time.
For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously
-working on the graph and its topological dual. We will show one more linear algorithm soon. The advantage
-of our approach is that we do not need to construct the planar embedding explicitly.
-
-\rem
-To achieve the linear time complexity, the algorithm needs a very careful implementation.
-Specifically, when we represent the graph using adjacency lists, whose heads are stored
-in an array indexed by vertex identifiers, we must renumber the vertices in each iteration.
-Otherwise, unused elements could end up taking most of the space in the arrays and the scans of these
-arrays would have super-linear cost with respect to the size of the current graph~$G_i$.
+working on the graph and its topological dual. The advantage of our approach is that we do not need
+to construct the planar embedding explicitly. We will show one more linear algorithm
+in section~\ref{minorclosed}.
\rem
-The algorithm can be also implemented on the pointer machine. Representation of graphs
-by pointer structures easily avoids the aforementioned problems with sparse arrays,
-but we need to handle the bucket sorting somehow. We can create a small data structure
-for every vertex and use a pointer to this structure as a unique identifier of the vertex.
-We will also keep a list of all vertex structures. During the bucket sort, each vertex
-structure will contain a pointer to the corresponding bucket and the vertex list will
-define the order of vertices (which can be arbitrary).
+To achieve the linear time complexity, the algorithm needs a very careful implementation,
+but we defer the technical details to section~\ref{bucketsort}.
+\para
Graph contractions are indeed a~very powerful tool and they can be used in other MST
algorithms as well. The following lemma shows the gist:
edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
\qed
-\section{Minor-closed graph classes}
-
-The contracting algorithm given in the previous section has been found to perform
-well on planar graphs, but in the general case its time complexity was not linear.
-Can we find any broader class of graphs where the algorithm is still efficient?
-The right context turns out to be the minor-closed graph classes, which are
-closed under contractions and have bounded density.
-
-\defn
-A~graph~$H$ is a \df{minor} of a~graph~$G$ iff it can be obtained
-from a subgraph of~$G$ by a sequence of simple graph contractions (see \ref{simpcont}).
-
-\defn
-A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and
-its every minor~$H$, the graph~$H$ lies in~$\cal C$ as well. A~class~$\cal C$ is called
-\df{non-trivial} if at least one graph lies in~$\cal C$ and at least one lies outside~$\cal C$.
-
-\example
-Non-trivial minor-closed classes include planar graphs and more generally graphs
-embeddable in any fixed surface. Many nice properties of planar graphs extend
-to these classes, too, most notably the linearity of the number of edges.
-
-\defn\id{density}%
-Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$
-to be the infimum of all~$\varrho$'s such that $m(G) \le \varrho\cdot n(G)$
-holds for every $G\in\cal C$.
-
-\thmn{Density of minor-closed classes}
-A~minor-closed class of graphs has finite edge density if and only if it is
-a non-trivial class.
-
-\proof
-See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions.
-\qed
-
-\thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}%
-For any fixed non-trivial minor-closed class~$\cal C$ of graphs, Algorithm \ref{contbor} finds
-the MST of any graph in this class in time $\O(n)$. (The constant hidden in the~$\O$
-depends on the class.)
-
-\proof
-Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered
-by the algorithm at the beginning of the $i$-th iteration by~$G_i$ and its number of vertices
-and edges by $n_i$ and $m_i$ respectively. Again the $i$-th phase runs in time $\O(m_i)$
-and $n_i \le n/2^i$, so it remains to show a linear bound for the $m_i$'s.
-
-Since each $G_i$ is produced from~$G_{i-1}$ by a sequence of edge contractions,
-all $G_i$'s are minors of~$G$.\foot{Technically, these are multigraph contractions,
-but followed by flattening, so they are equivalent to contractions on simple graphs.}
-So they also belong to~$\cal C$ and by the previous theorem $m_i\le \varrho({\cal C})\cdot n_i$.
-\qed
-
-\rem\id{nobatch}%
-The contractive algorithm uses ``batch processing'' to perform many contractions
-in a single step. It is also possible to perform contractions one edge at a~time,
-batching only the flattenings. A~contraction of an edge~$uv$ can be done
-in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back
-with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small
-degrees. The following lemma shows that this is always the case in minor-closed
-classes.
-
-\lemman{Low-degree vertices}\id{lowdeg}%
-Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph
-with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$.
-
-\proof
-Assume the contrary: Let there be at least $n/2$ vertices with degree
-greater than~$4\varrho$. Then $\sum_v \deg(v) > n/2
-\cdot 4\varrho = 2\varrho n$, which is in contradiction with the number
-of edges being at most $\varrho n$.
-\qed
-
-\rem
-The proof can be also viewed
-probabilistically: let $X$ be the degree of a vertex of~$G$ chosen uniformly at
-random. Then ${\bb E}X \le 2\varrho$, hence by the Markov's inequality
-${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have
-$\deg(v)\le 4\varrho$.
-
-\algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}%
-\algo
-\algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
-\:$T\=\emptyset$.
-\:$\ell(e)\=e$ for all edges~$e$.
-\:While $n(G)>1$:
-\::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
-\:::Select the lightest edge~$e$ incident with~$v$.
-\:::Contract~$G$ along~$e$.
-\:::$T\=T + \ell(e)$.
-\::Flatten $G$, removing parallel edges and loops.
-\algout Minimum spanning tree~$T$.
-\endalgo
-
-\thm
-When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the
-Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$
-finds the MST of any graph from this class in time $\O(n)$. (The constant
-in the~$\O$ depends on~the class.)
-
-\proof
-Let us denote by $G_i$, $n_i$ and $m_i$ the graph considered by the
-algorithm at the beginning of the $i$-th iteration of the outer loop,
-and the number of its vertices and edges respectively. As in the proof
-of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s
-are minors of the graph~$G$ given as the input.
-
-For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
-guarantees that at least $n_i/2$ edges get selected in the $i$-th iteration.
-Hence at least a half of the vertices participates in contractions, so
-$n_i\le 3/4\cdot n_{i-1}$. Therefore $n_i\le n\cdot (3/4)^i$ and the algorithm terminates
-after $\O(\log n)$ iterations.
-
-Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
-the trivial cut $\delta(v)$ (see the Blue Rule in \ref{rbma}).
-The steps 6 and~7 therefore correspond to the operation
-described by the Lemma on contraction of MST edges (\ref{contlemma}) and when
-the algorithm stops, $T$~is indeed the minimum spanning tree.
-
-It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have
-$m_i\le \varrho n_i \le \varrho n/2^i$.
-We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
-Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
-over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$.
-Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting
-Bor\o{u}vka's Algorithm (see \ref{contiter}).
-
-The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
-\qed
-
-\rem
-For planar graphs, we can get a sharper version of the low-degree lemma,
-showing that the algorithm works with $t=8$ as well (we had $t=12$ as
-$\varrho=3$). While this does not change the asymptotic time complexity
-of the algorithm, the constant-factor speedup can still delight the hearts of
-its practical users.
-
-\lemman{Low-degree vertices in planar graphs}%
-Let $G$ be a planar graph with $n$~vertices. Then at least $n/2$ vertices of~$v$
-have degree at most~8.
-
-\proof
-It suffices to show that the lemma holds for triangulations (if there
-are any edges missing, the situation can only get better) with at
-least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$.
-The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
-so by the same argument as in the proof of the general lemma, for at least $n/2$
-vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$.
-\qed
-
-\rem\id{hexa}%
-The constant~8 in the previous lemma is the best we can have.
-Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them
-lie on the outer face and have degrees at most~6, the remaining $n-\O(k)$ interior
-vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$,
-ignoring terms of order $\O(k)$. All interior triangles can be properly colored with
-two colors, black and white. Now add a~new vertex inside each white face and connect
-it to all three vertices on the boundary of that face. This adds $f/2 \approx n$
-vertices of degree~3 and it increases the degrees of the original $\approx n$ interior
-vertices to~9, therefore about a half of the vertices of the new planar graph
-has degree~9.
-
-\figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
-
-
-\section{Using Fibonacci heaps}
-\id{fibonacci}
-
-% G has to be connected, so m=O(n)
-% mention Steiner trees
-% mention matroids
-% sorted weights
-% \O(...) as a set?
-% impedance mismatch in terminology: contraction of G along e vs. contraction of e.
-% use \delta(X) notation
-% mention disconnected graphs
-%%% fix off by 1 errors in the distractors
-
\endpart
projects / saga.git / blobdiff