More Fibonacci.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index b8396b2e2ae1ace5db61a91dedceeafa16872ccc..9bde5ab6b78c868ebdb34c28755aba3dd0c18e84 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -595,6 +595,7 @@ We will also keep a list of all vertex structures. During the bucket sort, each
 structure will contain a pointer to the corresponding bucket and the vertex list will
 define the order of vertices (which can be arbitrary).
 
+\para
 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:
 
@@ -944,8 +945,22 @@ authors claim implementation advantages.
 
 \FIXME{Mention Thorup's Fibonacci-like heaps for integers?}
 
+\rem
+For sparse graphs, we can cross-breed this algorithm with the contractive
+Bor\o{u}vka's algorithm: First perform $\log\log n$ steps of contractive
+Bor\o{u}vka, which takes $\O(m\log\log n)$ time and produces a~graph~$G'$
+with $m'\le m$ and $n'\le n/\log n$. Then run Algorithm~\ref{jarniktwo} on~$G'$
+and it finishes in time $\O(m'+n'\log n') = \O(m)$. Finally combine MST edges
+found by both algorithms to a~single tree as in~the Contraction lemma (\ref{contlemma}).
+
+\para Xyzzy.
+
+\FIXME{Describe the heap limitation trick and the $\O(m\beta(m,n))$ algorithm.}
+
+
 
 
+% use \para
 % G has to be connected, so m=O(n)
 % mention Steiner trees
 % mention matroids