-%--------------------------------------------------------------------------------
-
-\section{Special cases and related problems}
-
-Finally, we will focus our attention on various special cases of the minimum
-spanning tree problem which frequently arise in practice.
-
-\examplen{Graphs with sorted edges}
-When the edges are already sorted by their weights, we can use the Kruskal's
-algorithm to find the MST in time $\O(m\timesalpha(n))$ (Theorem \ref{kruskal}).
-We however can do better: As the minimality of a~spanning tree depends only on the
-order of weights and not on the actual values (Theorem \ref{mstthm}), we can
-renumber the weights to $1, \ldots, m$ and find the MST using the Fredman-Willard
-algorithm for integer weights. According to Theorem \ref{intmst} it runs in
-time $\O(m)$ on the Word-RAM.
-
-\examplen{Graphs with a~small number of distinct weights}
-When the weights of edges are drawn from a~set of a~fixed size~$U$, we can
-sort them in linear time and so reduce the problem to the previous case.
-A~more practical way is to use the Jarn\'\i{}k's algorithm (\ref{jarnimpl}),
-but replace the heap by an~array of $U$~buckets. As the number of buckets
-is constant, we can find the minimum in constant time and hence the whole
-algorithm runs in time $\O(m)$, even on the Pointer Machine. For large
-values of~$U,$ we can build a~binary search tree or the van Emde-Boas
-tree (see Section \ref{ramdssect} and \cite{boas:vebt}) on the top of the buckets to bring the complexity
-of finding the minimum down to $\O(\log U)$ or $\O(\log\log U)$ respectively.
-
-\examplen{Graphs with floating-point weights}
-A~common case of non-integer weights are rational numbers in floating-point (FP)
-representation. Even in this case we will be able to find the MST in linear time.
-The most common representation of binary FP numbers specified by the IEEE
-standard 754-1985 \cite{ieee:binfp} has a~useful property: When the
-bit strings encoding non-negative FP numbers are read as ordinary integers,
-the order of these integers is the same as of the original FP numbers. We can
-therefore once again replace the edge weights by integers and use the linear-time
-integer algorithm. While the other FP representations (see \cite{dgoldberg:fp} for
-an~overview) need not have this property, the corresponding integers can be adjusted
-in $\O(1)$ time to the format we need. (More advanced tricks of this type have been
-employed by Thorup in \cite{thorup:floatint} to extend his linear-time algorithm
-for single-source shortest paths to FP edge lengths.)
-
-\examplen{Graphs with bounded degrees}
-For graphs with vertex degrees bounded by a~constant~$\Delta$, the problem is either
-trivial (if $\Delta<3$) or as hard as for arbitrary graphs. There is a~simple linear-time
-transform of arbitrary graphs to graphs with maximum degree~3 which preserves the MST:
-
-\lemman{Degree reduction}\id{degred}%
-For every graph~$G$ there exists a~graph~$G'$ with maximum degree at most~3 and
-a~function $\pi: E(G)\rightarrow E(G')$ such that $\mst(G) = \pi^{-1}(\mst(G'))$.
-The graph $G'$ and the embedding~$\pi$ can be constructed in time $\O(m)$.
-
-\figure{french.eps}{\epsfxsize}{Degree reduction in Lemma~\ref{degred}}
-
-\proof
-We show how to eliminate a~single vertex~$v$ of degree $d>3$ and then apply
-induction.
-
-Assume that $v$~has neighbors $w_1,\ldots,w_d$. We replace~$v$ and the edges~$vw_i$
-by $d$~new vertices $v_1,\ldots,v_d$, joined by a~path $v_1v_2\ldots v_d$, and
-edges~$v_iw_i$. Each edge of the path will receive a~weight smaller than all
-original weights, the other edges will inherit the weights of the edges $vw_i$
-they replace. The edges of the path will therefore lie in the MST (this is
-obvious from the Kruskal's algorithm) and as~$G$ can be obtained from the
-new~$G'$ by contracting the path, the rest follows from the Contraction lemma
-(\ref{contlemma}).
-
-This step can be carried out in time $\O(d)$. As it replaces a high-degree
-vertex by vertices of degree~3, the whole procedure stops in at most~$n$ such
-steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$ including the
-time needed to find the high-degree vertices at the beginning.
-\qed
-
-\examplen{Euclidean MST}
-The MST also has its counterparts in the realm of geometric algorithms. Suppose
-that we have $n$~points $x_1,\ldots,x_n$ in the plane and we want to find the
-shortest system of segments connecting these points. If we want the segments to
-touch only in the given points, this is equivalent to finding the MST of the
-complete graph on the vertices $V=\{x_1,\ldots,x_n\}$ with edge weights
-defined as the Euclidean distances of the points. Since the graph is dense, many of the MST
-algorithms discussed run in linear time with the size of the graph, hence
-in time $\O(n^2)$.
-
-There is a~more efficient method based on the observation that the MST
-is always a~subgraph of the Delaunay's tesselation for the given points
-(this was first noted by Shamos and Hoey in~\cite{shamos:closest}). The
-tesselation is a~planar graph, which guarantees that it has $\O(n)$ edges,
-and it is a~dual graph of the Voronoi diagram of the given points, which can
-be constructed in time $\O(n\log n)$ using for example the Fortune's
-algorithm \cite{fortune:voronoi}. We can therefore reduce the problem
-to finding the MST of the tesselation for which $\O(n\log n)$ time
-is more than sufficient.
-
-This approach fails for non-Euclidean metrics, but in some cases
-(in particular for the rectilinear metric) the $\O(n\log n)$ time bound
-is also achievable by the algorithm of Zhou et al.~\cite{zhou:nodel}
-based on the sweep-line technique and the Red rule. For other
-variations on the geometric MST, see Eppstein's survey paper
-\cite{eppstein:spanning}.
-
-\examplen{Steiner trees}
-The constraint that the segments in the previous example are allowed to touch
-each other only in the given points looks artificial and it is indeed uncommon in
-practical applications (including the problem of designing electrical transmission
-lines originally studied by Bor\o{u}vka). If we lift this restriction, we get
-the problem known by the name Steiner tree.\foot{It is named after the Swiss mathematician
-Jacob Steiner who studied a~special case of this problem in the 19th century.}
-We can also define it in terms of graphs:
-
-\defn A~\df{Steiner tree} of a~weighted graph~$(G,w)$ with a~set~$M\subseteq V$
-of \df{mandatory notes} is a~tree~$T\subseteq G$ that contains all the mandatory
-vertices and its weight is minimum possible.
-
-For $M=V$ the Steiner tree is identical to the MST, but if we allow an~arbitrary
-choice of the mandatory vertices, it is NP-hard. This has been proven by Garey and Johnson
-\cite{garey:steiner,garey:rectisteiner} for not only the graph version with
-weights $\{1,2\}$, but also for the planar version with Euclidean or rectilinear
-metric. There is a~polynomial approximation algorithm with ratio $5/3$ for
-graphs due to Pr\"omel and Steger \cite{proemel:steiner} and a~polynomial-time
-approximation scheme for the Euclidean Steiner tree in an~arbitrary dimension
-by Arora \cite{arora:tspapx}.
-
-\examplen{Approximating the weight of the MST}
-Sometimes we are not interested in the actual edges forming the MST and only
-the weight matters. If we are willing to put up with a~randomized approximation,
-we can even achieve sub-linear complexity. Chazelle et al.~\cite{chazelle:mstapprox}
-have shown an~algorithm which, given $0 < \varepsilon < 1/2$, approximates
-the weight of the MST of a~graph with average degree~$d$ and edge weights from the set
-$\{1,\ldots,w\}$ in time $\O(dw\varepsilon^{-2}\cdot\log(dw/\varepsilon))$,
-producing a~weight which has relative error at most~$\varepsilon$ with probability
-at least $3/4$. They have also proven an~almost matching lower bound $\Omega(dw\varepsilon^{-2})$.
-
-For the $d$-dimensional Euclidean case, there is a~randomized approximation
-algorithm by Czumaj et al.~\cite{czumaj:euclidean} which with high probability
-produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\sqrt{n}\cdot \poly(1/\varepsilon))$\foot{%
-$\widetilde\O(f) = \O(f\cdot\log^{\O(1)} f)$ and $\poly(n)=n^{\O(1)}$.}
-queries to a~data structure containing the points. The data structure is expected
-to answer orthogonal range queries and cone approximate nearest neighbor queries.
-There is also a~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation
-algorithm for the MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}.
-(This is still sub-linear since the corresponding graph has roughly $n^2$ edges.)
-