X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=opt.tex;h=86402c617a708fe47db3e157138d6623f74e16af;hb=36012b9518adaee9da67e653cbc01f541a1273bf;hp=632fd4ee12631e10272c2f331c0371928716381b;hpb=3064137808233f772a75f3367c029ecde806455b;p=saga.git

diff --git a/opt.tex b/opt.tex
index 632fd4e..86402c6 100644
--- a/opt.tex
+++ b/opt.tex
@@ -6,10 +6,21 @@
 
 \section{Soft heaps}
 
+A~vast majority of MST algorithms that we have encountered so far is based on
+the Tarjan's Blue rule (Lemma \ref{bluelemma}). The rule serves to identify
+edges that belong to the MST, while all other edges are left in the process. This
+unfortunately means that the later stages of computation spend most of
+their time on these useless edges. A~notable exception is the randomized
+algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses
+Red rule (Lemma \ref{redlemma}) to filter out edges that are guaranteed to stay
+outside the MST, so that the graphs with which the algorithm works get smaller
+with time.
+
 Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}
-have presented algorithms for the MST with worst-case time complexity
+have presented new deterministic algorithms for the MST which are also based
+on the combination of both rules. They have reached worst-case time complexity
 $\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to their results
-and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal},
+and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal}
 which is provably optimal.
 
 At the very heart of all these algorithms lies the \df{soft heap} discovered by
@@ -588,7 +599,7 @@ Let us show that edges of~$G$ that do not belong to the right-hand side
 do not belong to the left-hand side either.
 We know that the edges that
 do not participate in the MSF of some graph are exactly those which are the heaviest
-on some cycle (this is the Cycle rule, \ref{cyclerule}).
+on some cycle (this is the Cycle rule from Lemma \ref{redlemma}).
 
 Whenever an~edge~$g$ lies in~$C$, but not in~$\msf(C)$, then $g$~is the heaviest edge
 on some cycle in~$C$. As this cycle is also contained in~$G$, the edge $g$~does not participate
@@ -793,7 +804,7 @@ computation results in the real MSF of~$G$ with the particular weights.
 The \df{time complexity} of a~decision tree is defined as its depth. It therefore
 bounds the number of comparisons spent on every path. (It need not be equal since
 some paths need not correspond to an~actual computation --- the sequence of outcomes
-on the path could be unsatifisfiable.)
+on the path could be unsatisfiable.)
 
 A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
 among the correct decision trees for the given graph.
@@ -906,7 +917,7 @@ $H=\bigcup_i C_i$.
 The first and second condition of the definition of compartments follow
 from the Partitioning theorem (\ref{partthm}), so it remains to show that $\msf(H)$
 is the union of the MSF's of the individual compartments. By the Cycle rule
-(\ref{cyclerule}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
+(Lemma \ref{redlemma}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
 it is the heaviest edge on some cycle. It is therefore sufficient to prove that
 every cycle in~$H$ is contained within a~single~$C_i$.