Continuing with the intro to dynamic algorithms.

[saga.git] / opt.tex

diff --git a/opt.tex b/opt.tex
index 9de4d64a617cfd05943cdd07d4f3c0c29663d661..15b97d510b3796933ef1c5b137381fa208038cad 100644 (file)
--- a/opt.tex
+++ b/opt.tex
@@ -1123,6 +1123,16 @@ We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Cha
 or Pettie \cite{pettie:ackermann}.
 \qed
 
+Similarly to the Iterated Jarn\'\i{}k's algorithm, this bound is actually linear for classes of graphs
+that do not have density extremely close to constant:
+
+\cor
+The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot a(k,n)$ for any fixed~$k$.
+
+\proof
+Combine the previous theorem with Lemma \ref{alphaconst}.
+\qed
+
 \rem
 It is also known from \cite{pettie:optimal} that when we run the Optimal algorithm on a~random
 graph drawn from either $G_{n,p}$ (random graphs on~$n$ vertices, each edge is included with probability~$p$