Matroids.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 871d92df1e529adc4397ffc6b8530c2c717811f4..3f715954dd69cdaeb575751369442f8f562971f9 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -316,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}%