\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
-$\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},
+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}
which is provably optimal.
At the very heart of all these algorithms lies the \df{soft heap} discovered by
The soft heap contains a~set of distinct items from a~totally ordered universe and it
supports the following operations:
\itemize\ibull
-\:$\<Create>(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter~$\varepsilon$,
-\:$\<Insert>(H,x)$ --- insert a~new item~$x$ to the heap~$H$,
-\:$\<Meld>(P,Q)$ --- merge two heaps into one, more precisely move all items of a~heap~$Q$
- to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$),
-\:$\<DeleteMin>(H)$ --- delete the minimum item of the heap~$H$ and return its value
+\:$\<Create>(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$.
+\:$\<Insert>(H,x)$ --- Insert a~new item~$x$ to the heap~$H$.
+\:$\<Meld>(P,Q)$ --- Merge two heaps into one, more precisely move all items of a~heap~$Q$
+ to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$).
+\:$\<DeleteMin>(H)$ --- Delete the minimum item of the heap~$H$ and return its value
(optionally signalling that the value has been corrupted).
-\:$\<Explode>(H)$ --- destroy the heap and return a~list of all items contained in it
+\:$\<Explode>(H)$ --- Destroy the heap and return a~list of all items contained in it
(again optionally marking those corrupted).
\endlist
to cover the cost of all other operations.
All heap operations use only pointer operations, so it will be easy to derive the time
-bound in the Pointer machine model. The notable exception is however that the procedures
+bound in the Pointer Machine model. The notable exception is however that the procedures
often refer to the ranks, which are integers on the order of $\log n$, so they cannot
fit in a~single memory cell. For the time being, we will assume that the ranks can
be manipulated in constant time, postponing the proof for later.
\lemma\id{shyards}%
Every manipulation with ranks performed by the soft heap operations can be
-implemented on the Pointer machine in constant amortized time.
+implemented on the Pointer Machine in constant amortized time.
\proof
-We create a~``yardstick'' --- a~double linked list whose elements represent the possible
+We will recycle the idea of ``yardsticks'' from Section \ref{bucketsort}.
+We create a~yardstick --- a~doubly linked list whose elements represent the possible
values of a~rank. Every vertex of a~queue will store its rank as a~pointer to
the corresponding ``tick'' of the yardstick. We will extend the list as necessary.
\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
-in time $\O(n\log(1/\varepsilon))$ on the Pointer machine. At every moment, the
+in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
heap contains at most $\varepsilon n$ corrupted items.
\proof
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.
\lemman{Construction of optimal decision trees}\id{odtconst}%
An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
-the Pointer machine in time $\O(2^{2^{4n^2}})$.
+the Pointer Machine in time $\O(2^{2^{4n^2}})$.
\proof
We will try all possible decision trees of depth at most $2n^2$
The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
and each permutation can be checked in time $\O(\poly(n))$.
-On the Pointer machine, trees and permutations can be certainly enumerated in time
+On the Pointer Machine, trees and permutations can be certainly enumerated in time
$\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore
$\O(2^{2^{3n^2}} \cdot 2^{n^3} \cdot \poly(n)) = \O(2^{2^{4n^2}})$.
\qed
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$.
\:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph}
\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
\:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
-\:Run two iterations of the Contractive Bor\o{u}vka's algorithm (\ref{contbor}) on~$G_B$,
+\:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
\:$F_C \= \mst(G_C)$ obtained by a~recursive call to this algorithm.
\:Return $F_B \cup F_C$.
Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm})
and from the proofs of the respective algorithms used as subroutines. Let us take a~look at
-the time complexity. We will be careful to use only the operations offered by the Pointer machine.
+the time complexity. We will be careful to use only the operations offered by the Pointer Machine.
\lemma\id{optlemma}%
The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence:
The combined graph~$G_B$ has~$n$ vertices, but less than~$n$ edges from the
individual spanning trees and at most~$m/4$ additional edges which were
-corrupted. The iterations of the Bor\o{u}vka's algorithm on~$G_B$ take $\O(m)$
+corrupted. The Bor\o{u}vka steps on~$G_B$ take $\O(m)$
time by Lemma \ref{boruvkaiter} and they produce a~graph~$G_C$ with at most~$n/4$
vertices and at most $n/4 + m/4 \le m/2$ edges. (The $n$~tree edges in~$G_B$ are guaranteed
to be reduced by the Bor\o{u}vka's algorithm.) It is easy to verify that this
projects / saga.git / blobdiff