disciplines, the previous work was not well known and the algorithms had to be
rediscovered several times.
-Recently, several significantly faster algorithms were discovered, most notably the
-$\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}.
+In the next 50 years, several significantly faster algorithms were discovered, ranging
+from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
+over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
+and Pettie \cite{pettie:ackermann}, to another algorithm by Pettie \cite{pettie:optimal}
+whose time complexity is provably optimal.
-\FIXME{Write the rest of the history.}
-
-This chapter attempts to survey the important algorithms for finding the MST and it
-also presents several new ones.
+In the upcoming chapters, we will explore this colorful universe of MST algorithms.
+We will meet the standard works of the classics, the clever ideas of their successors,
+various approaches to the problem including randomization and solving of important
+special cases.
%--------------------------------------------------------------------------------
-\section{Basic properties}
+\section{Basic properties}\id{mstbasics}%
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
Theorem \ref{mstthm}), so it is the heaviest edge on the cycle $T_{min}[e]+e$.
\qed
+\rem
+The MST problem is a~special case of the problem of finding the minimum basis
+of a~weighted matroid. Surprisingly, when we modify the Red-Blue procedure to
+use the standard definitions of cycles and cuts in matroids, it will always
+find the minimum basis. Some of the other MST algorithms also easily generalize to
+matroids and in some sense matroids are exactly the objects where ``the greedy approach works''. We
+will however not pursue this direction in our work, referring the reader to the Oxley's monograph
+\cite{oxley:matroids} instead.
+
%--------------------------------------------------------------------------------
\section{Classical algorithms}\id{classalg}%
Jarn\'\i{}k's algorithm finds the MST of a~given graph in time $\O(m\log n)$.
\rem
-We will show several faster implementations in section \ref{fibonacci}.
+We will show several faster implementations in section \ref{iteralg}.
\paran{Kruskal's algorithm}%
The last of the three classical algorithms processes the edges of the
of vertices and edges of this graph by $n_i$ and $m_i$ respectively.
\lemma\id{contiter}%
-The $i$-th iteration of the algorithm (also called the Bor\o{u}vka step) can be carried
+The $i$-th iteration of the algorithm (also called the \df{Bor\o{u}vka step}) can be carried
out in time~$\O(m_i)$.
\proof
To achieve the linear time complexity, the algorithm needs a very careful implementation,
but we defer the technical details to section~\ref{bucketsort}.
-\para
+\paran{General contractions}%
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:
\rem
In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$.
-\para
+\paran{A~lower bound}%
Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity
is tight. The graphs do not have unique weights, but they are constructed in a way that
the algorithm never compares two edges with the same weight. Therefore, when two such