Matroids.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 9f8a7414bc097bba7a59f91e324daf9408d3e1f2..3f715954dd69cdaeb575751369442f8f562971f9 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -41,19 +41,20 @@ 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.
 
 %--------------------------------------------------------------------------------
 
-\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
@@ -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
@@ -491,7 +501,7 @@ so we perform $\<Union>(u,v)$ to merge the equivalence classes.
 Tarjan and van Leeuwen have shown that there is a~data structure for the DSU problem
 with surprising efficiency:
 
-\thmn{Disjoint Set Union, Tarjan and van Leeuwen \cite{tarjan:setunion}}%
+\thmn{Disjoint Set Union, Tarjan and van Leeuwen \cite{tarjan:setunion}}\id{dfu}%
 Starting with a~trivial equivalence with single-element classes, a~sequence of operations
 comprising of $n$~\<Union>s intermixed with $m\ge n$~\<Find>s can be processed in time
 $\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's function
@@ -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