\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
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
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.
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$.
projects / saga.git / blobdiff