Matroids.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 2cfe5d0f7820bd5642ac9cf4879a35c32e90a6a1..3f715954dd69cdaeb575751369442f8f562971f9 100644 (file)
--- 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}%
@@ -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