X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=mst.tex;h=3f715954dd69cdaeb575751369442f8f562971f9;hb=2fcd9085adda5a37aa64731121c0206780586cca;hp=963e068bfb3dd7ac491d24a59e52951148f86958;hpb=13bbbd56bd577b4d5bb856da3ab6e1ae6392300d;p=saga.git

diff --git a/mst.tex b/mst.tex
index 963e068..3f71595 100644
--- a/mst.tex
+++ b/mst.tex
@@ -41,15 +41,16 @@ spanning tree problem was one of the central topics of the flourishing new
 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.
 
 %--------------------------------------------------------------------------------
 
@@ -315,6 +316,15 @@ direction, when~$e$ is not contained in~$T_{min}$, it is $T_{min}$-heavy (by
 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}%
@@ -439,7 +449,7 @@ From this, we can conclude:
 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
@@ -583,7 +593,7 @@ at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and th
 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
@@ -640,7 +650,7 @@ in section~\ref{minorclosed}.
 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:
 
@@ -667,7 +677,7 @@ which obviously works in multigraphs as well.)
 \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