From 2fcd9085adda5a37aa64731121c0206780586cca Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 19 Apr 2008 18:22:03 +0200
Subject: [PATCH] Matroids.

---
 PLAN       | 6 ------
 biblio.bib | 6 ++++++
 mst.tex    | 9 +++++++++
 3 files changed, 15 insertions(+), 6 deletions(-)

diff --git a/PLAN b/PLAN
index e333a50..f351b24 100644
--- a/PLAN
+++ b/PLAN
@@ -68,12 +68,6 @@ Related:
 - K best trees
 - degree-restricted cases and arborescences
 - bounded expansion classes?
-- mention matroids
-
-Models:
-
-- add references to the C language
-- all data structures should mention space complexity
 
 Ranking:
 
diff --git a/biblio.bib b/biblio.bib
index f97c59c..3dead5b 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -1477,3 +1477,9 @@
     type = "Memo"
 }
 
+@book{ oxley:matroids,
+  title={{Matroid Theory}},
+  author={Oxley, J.G.},
+  year={1992},
+  publisher={Oxford University Press}
+}
diff --git a/mst.tex b/mst.tex
index 871d92d..3f71595 100644
--- 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}%
-- 
2.39.2