Forgotten mjalpha.bst.

[saga.git] / opt.tex

diff --git a/opt.tex b/opt.tex
index 18e50535b27387165afa93201ab3bbe5ff068ce7..bf30371d6fc71f2c75059b7369f056f78e8bad3d 100644 (file)
--- a/opt.tex
+++ b/opt.tex
@@ -2,14 +2,25 @@
 \input macros.tex
 \fi
 
 \input macros.tex
 \fi
 

-\chapter{Approaching Optimality}
+\chapter{Approaching Optimality}\id{optchap}%

 
 

-\section{Soft heaps}
+\section{Soft heaps}\id{shsect}%
+
+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 edges that never enter the MSF. A~notable exception is the randomized
+algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses
+the 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}
 
 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
 which is provably optimal.
 
 At the very heart of all these algorithms lies the \df{soft heap} discovered by


@@ -18,38 +29,50 @@ similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
 the expense of \df{corrupting} a~fraction of the inserted elements by raising
 their values (the values are however never lowered). This allows for
 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
 the expense of \df{corrupting} a~fraction of the inserted elements by raising
 their values (the values are however never lowered). This allows for

-an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$.
+a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$.

 The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
 The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every

-moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be
+moment at most~$\varepsilon n$ elements of the $n$~elements inserted can be

 corrupted.
 
 corrupted.
 

-\defnn{Soft heap operations}%
-The soft heap contains a~set of distinct items from a~totally ordered universe and it
+\defnn{Soft heap interface}%
+The \df{soft heap} contains a~set of distinct items from a~totally ordered universe and it

 supports the following operations:
 \itemize\ibull
 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$ into 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).
   (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
 
   (again optionally marking those corrupted).
 \endlist
 

+\>For every item, we will distinguish between its \df{original} value at the time
+of insertion and its \df{current} value in the heap, which is possibly corrupted.
+

 \examplen{Linear-time selection}
 We can use soft heaps to select the median (or generally the $k$-th smallest element)
 of a~sequence. We insert all $n$~elements to a~soft heap with error rate $\varepsilon=1/3$.
 \examplen{Linear-time selection}
 We can use soft heaps to select the median (or generally the $k$-th smallest element)
 of a~sequence. We insert all $n$~elements to a~soft heap with error rate $\varepsilon=1/3$.

-Then we delete the minimum about $n/3$ times and we remember the current (possibly corrupted)
-value~$x$ of the last element deleted. This~$x$ is greater or equal than the current
-values of the previously deleted elements and thus also than their correct values.
+Then we delete the minimum about $n/3$ times and we remember the current value~$x$
+of the last element deleted. This~$x$ is greater or equal than the current
+values of the previously deleted elements and thus also than their original values.

 On the other hand, the current values of the $2n/3$ elements remaining in the heap
 are greater than~$x$ and at most $n/3$ of them are corrupted. Therefore at least $n/3$
 On the other hand, the current values of the $2n/3$ elements remaining in the heap
 are greater than~$x$ and at most $n/3$ of them are corrupted. Therefore at least $n/3$

-elements are greater than~$x$ and at least $n/3$ ones are smaller. Depending on the value
-of~$k$, we can always throw away one of these parts and recurse on the rest (similarly to
-the Hoare's Quickselect algorithm \cite{hoare:qselect}). The total time complexity will
-be $\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$. We have obtained a~nice alternative to the standard
-linear-time selection algorithm by Blum \cite{blum:selection}. The same trick can be used
+original elements are greater than~$x$ and at least $n/3$ ones are smaller.
+
+This allows us to use the~$x$ as a~pivot in the traditional divide-and-conquer algorithm
+for selection (cf.~Hoare's Quickselect algorithm \cite{hoare:qselect}): We split the
+input elements to three parts: $A$~contains those less than~$x$, $B$~those equal to~$x$
+and $C$~those greater than~$x$. If $k\le\vert A\vert$, the desired element lies in~$A$,
+so we can continue by finding the $k$-th smallest element of~$A$. If $\vert A\vert < k \le \vert
+A\vert + \vert B\vert$, the desired element is $x$~itself. Otherwise, we search for the
+$(k-\vert A\vert-\vert B\vert)$-th smallest element of~$C$. Either way, we have removed
+at least $n/3$ items, so the total time complexity is
+$\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$.
+
+We have obtained a~nice alternative to the standard
+linear-time selection algorithm of Blum \cite{blum:selection}. The same trick can be used

 to select a~good pivot in Quicksort \cite{hoare:qsort}, leading to time complexity $\O(n\log n)$
 in the worst case.
 
 to select a~good pivot in Quicksort \cite{hoare:qsort}, leading to time complexity $\O(n\log n)$
 in the worst case.
 


@@ -68,8 +91,8 @@ permanently occupied. The left sons will be called \df{white}, the right ones
 
 The first value in every list is called the \df{controlling key} of the vertex,
 denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
 
 The first value in every list is called the \df{controlling key} of the vertex,
 denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used

-value or we set $\<ckey>(v)=+\infty$. The \<ckey> obey the standard \df{heap order}
---- a~\<ckey> of a~parent is always smaller than the \<ckey>'s of its sons.
+value or we set $\<ckey>(v)=+\infty$. The \<ckey>s obey the standard \df{heap order}
+--- a~\<ckey> of a~parent is always smaller than the \<ckey>s of its sons.

 
 Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
 The ranks of leaves are always zero, the rank of every internal vertex can be
 
 Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
 The ranks of leaves are always zero, the rank of every internal vertex can be


@@ -93,7 +116,7 @@ ranks, colors and the ancestor relation.
 The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
 two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
 of the original roots and also its \<ckey>. To preserve the heap order, we will choose
 The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
 two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
 of the original roots and also its \<ckey>. To preserve the heap order, we will choose

-the one whose \<ckey> is smaller.
+the son whose \<ckey> is smaller.

 
 Sometimes, we will also need to split a~queue to smaller queues. We will call this operation
 \df{dismantling} the queue and it will happen only in cases when the item list in the root
 
 Sometimes, we will also need to split a~queue to smaller queues. We will call this operation
 \df{dismantling} the queue and it will happen only in cases when the item list in the root


@@ -126,8 +149,8 @@ its leftmost path contains at least~$k/2$ vertices.
 the heap of the smaller rank and we insert its queues to the other heap.
 If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
 a~single queue of rank~$k+1$ as already described and we propagate the new queue as
 the heap of the smaller rank and we insert its queues to the other heap.
 If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
 a~single queue of rank~$k+1$ as already described and we propagate the new queue as

-a~\df{carry} to the next iteration, similarly to addition of binary numbers.
-Finally we have to update the suffix minima by walking the new list backwards
+a~\df{carry} to the next iteration. (This is similar to addition of binary numbers.)
+Finally, we have to update the suffix minima by walking the new list backwards

 from the last inserted item.
 
 \em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
 from the last inserted item.
 
 \em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating


@@ -145,7 +168,7 @@ a~single-element heap and melding it to the destination heap.
 \algn{Melding of two soft heaps}
 \algo
 \algin Two soft heaps~$P$ and~$Q$.
 \algn{Melding of two soft heaps}
 \algo
 \algin Two soft heaps~$P$ and~$Q$.

-\:If $\<rank>(P) < \<rank>(Q)$, exchange the item lists of~$P$ and~$Q$.
+\:If $\<rank>(P) < \<rank>(Q)$, exchange the queue lists of~$P$ and~$Q$.

 \:$p\=\<head>(P)$.
 \brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that
 there is an~empty queue of infinite rank there.}
 \:$p\=\<head>(P)$.
 \brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that
 there is an~empty queue of infinite rank there.}


@@ -178,7 +201,7 @@ there is an~empty queue of infinite rank there.}
 \algout An~updated heap~$H$.
 \endalgo
 
 \algout An~updated heap~$H$.
 \endalgo
 

-\para
+\paran{Corruption}%

 So far, the mechanics of the soft heaps were almost identical to the binomial heaps
 and the reader could rightfully yawn. The things are going to get interesting
 now as we approach the parts where corruption of items takes place.
 So far, the mechanics of the soft heaps were almost identical to the binomial heaps
 and the reader could rightfully yawn. The things are going to get interesting
 now as we approach the parts where corruption of items takes place.


@@ -202,7 +225,7 @@ the higher is the rank, the longer list will be allowed.
 \<ckey>. There we look inside the item list of the root of the queue. We remove the \em{last}
 item from the list (we do not want the \<ckey> to change) and we return it as the minimum.
 (It is not necessarily the real minimum of all items, but always the minimum of their
 \<ckey>. There we look inside the item list of the root of the queue. We remove the \em{last}
 item from the list (we do not want the \<ckey> to change) and we return it as the minimum.
 (It is not necessarily the real minimum of all items, but always the minimum of their

-possibly corrupted values.)
+current, possibly corrupted values.)

 
 If the list becomes empty, we \em{refill} it with items from the lower levels of the
 same queue. This process can be best described recursively: We ask the left son to refill itself
 
 If the list becomes empty, we \em{refill} it with items from the lower levels of the
 same queue. This process can be best described recursively: We ask the left son to refill itself


@@ -211,21 +234,22 @@ same queue. This process can be best described recursively: We ask the left son
 son's list to its parent. Otherwise, we exchange the sons and move the list from the
 new left son to the parent. This way we obey the heap order and at the same time we keep
 the white left son free of items.
 son's list to its parent. Otherwise, we exchange the sons and move the list from the
 new left son to the parent. This way we obey the heap order and at the same time we keep
 the white left son free of items.

+\looseness=1  %%HACK%%

 
 

-Ocassionally, we repeat this process once again and we concatenate the resulting lists
-(we append the latter list to the former, using the smaller of the two \<ckey>'s). This
+Occasionally, we repeat this process once again and we concatenate the resulting lists
+(we append the latter list to the former, using the smaller of the two \<ckey>s). This

 makes the lists grow longer and we want to do that roughly on every other level of the
 tree. The exact condition will be that either the rank of the current vertex is odd,
 or the difference in ranks between this vertex and its right son is at least two.
 
 If refilling of the left son fails because there are no more items in that subtree
 makes the lists grow longer and we want to do that roughly on every other level of the
 tree. The exact condition will be that either the rank of the current vertex is odd,
 or the difference in ranks between this vertex and its right son is at least two.
 
 If refilling of the left son fails because there are no more items in that subtree

-(we report this by setting its \<ckey> to $+\infty$), the current vertex is no longer
+(we report this by setting the \<ckey> to $+\infty$), the current vertex is no longer

 needed --- the items would just pass through it unmodified. We therefore want to
 remove it. Instead of deleting it directly, we rather make it point to its former
 needed --- the items would just pass through it unmodified. We therefore want to
 remove it. Instead of deleting it directly, we rather make it point to its former

-grandsons and we remove the (now orhpaned) original son. This helps us to ensure
+grandsons and we remove the (now orphaned) original son. This helps us to ensure

 that both sons always keep the same rank, which will be useful for the analysis.
 
 that both sons always keep the same rank, which will be useful for the analysis.
 

-When all refilling is done, we update the suffix minima by walking from the current
+When the refilling is over, we update the suffix minima by walking from the current

 queue to the head of the heap exactly as we did in the \<Meld> procedure.
 
 Our only remaining worry is that the Rank invariant can be broken after the
 queue to the head of the heap exactly as we did in the \<Meld> procedure.
 
 Our only remaining worry is that the Rank invariant can be broken after the


@@ -236,14 +260,15 @@ empty. We will therefore move this check before the refilling of the root list.
 It will turn out that we have enough time to always walk the leftmost path
 completely, so no explicit counters are needed.
 
 It will turn out that we have enough time to always walk the leftmost path
 completely, so no explicit counters are needed.
 

-Let us translate these ideas to real (pseudo)code:
+%%HACK%%
+\>Let us translate these ideas to real (pseudo)code:

 
 \algn{Deleting the minimum item from a~soft heap}
 \algo
 \algin A~soft heap~$H$.
 \:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
 \:Remove the final element~$x$ of the item list in the root of~$q$.
 
 \algn{Deleting the minimum item from a~soft heap}
 \algo
 \algin A~soft heap~$H$.
 \:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
 \:Remove the final element~$x$ of the item list in the root of~$q$.

-\:If the item list is empty:
+\:If the item list became empty:

 \::Count the vertices on the leftmost path of~$q$.
 \::If there are less than $\<rank>(q)$ of them:
 \:::Remove~$q$ from the list of queues.
 \::Count the vertices on the leftmost path of~$q$.
 \::If there are less than $\<rank>(q)$ of them:
 \:::Remove~$q$ from the list of queues.


@@ -280,7 +305,7 @@ Let us translate these ideas to real (pseudo)code:
 all queues in the heap, walks the trees and the item lists of all vertices. It records
 all items seen, the corrupted ones are those that different from their \<ckey>.
 
 all queues in the heap, walks the trees and the item lists of all vertices. It records
 all items seen, the corrupted ones are those that different from their \<ckey>.
 

-\paran{Analysis of accuracy}
+\paran{Analysis of accuracy}%

 The description of the operations is now complete, so let us analyse their behavior
 and verify that we have delivered what we promised --- first the accuracy of
 the structure, then the time complexity of operations. In the whole analysis,
 The description of the operations is now complete, so let us analyse their behavior
 and verify that we have delivered what we promised --- first the accuracy of
 the structure, then the time complexity of operations. In the whole analysis,


@@ -296,9 +321,9 @@ satisfies:
 $$\ell(v) \le \max(1, 2^{\lceil \<rank>(v)/2 \rceil - r/2}).$$
 
 \proof
 $$\ell(v) \le \max(1, 2^{\lceil \<rank>(v)/2 \rceil - r/2}).$$
 
 \proof

-Initially, all item lists contain at most one item, so the ineqality trivially
-holds. Let us continue by induction. Melds can affect it only in the favorable
-direction (they ocassionally move an~item list to a~vertex of a~higher rank)
+Initially, all item lists contain at most one item, so the inequality trivially
+holds. Let us continue by induction. Melds can affect the inequality only in the favorable
+direction (they occasionally move an~item list to a~vertex of a~higher rank)

 and so do deletes (they only remove items from lists). The only potentially
 dangerous place is the \<Refill> procedure.
 
 and so do deletes (they only remove items from lists). The only potentially
 dangerous place is the \<Refill> procedure.
 


@@ -308,7 +333,7 @@ no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either
 $\<rank>(v)$ is odd or $\<rank>(w) < \<rank>(v)-1$ for any son~$w$ of~$v$ (remember
 that both sons have the same rank). In both cases, $\lceil\<rank>(w)/2\rceil \le
 \lceil\<rank>(v)/2\rceil - 1$. By the induction hypothesis, the size of each
 $\<rank>(v)$ is odd or $\<rank>(w) < \<rank>(v)-1$ for any son~$w$ of~$v$ (remember
 that both sons have the same rank). In both cases, $\lceil\<rank>(w)/2\rceil \le
 \lceil\<rank>(v)/2\rceil - 1$. By the induction hypothesis, the size of each

-of the two joined lists is at most $2^{\max(1,\lceil\<rank>(v)/2\rceil - 1 - r/2)}$,
+of the two lists being joined is at most $2^{\max(1,\lceil\<rank>(v)/2\rceil - 1 - r/2)}$,

 so the new list has at most $2^{\lceil\<rank>(v)/2\rceil - r/2}$ items. (The maximum
 has disappeared since $\<rank>(v)>r$ and therefore the desired bound is at least~2.)
 \qed
 so the new list has at most $2^{\lceil\<rank>(v)/2\rceil - r/2}$ items. (The maximum
 has disappeared since $\<rank>(v)>r$ and therefore the desired bound is at least~2.)
 \qed


@@ -348,13 +373,13 @@ last expression is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ blac
 this makes less than $n_k/2^{r-2}$ corrupted items as we asserted.
 \qed
 
 this makes less than $n_k/2^{r-2}$ corrupted items as we asserted.
 \qed
 

-\paran{Analysis of time complexity}
+\paran{Analysis of time complexity}%

 Now we will examine the amortized time complexity of the individual operations.
 We will show that if we charge $\O(r)$ time against every element inserted, it is enough
 to cover the cost of all other operations.
 
 All heap operations use only pointer operations, so it will be easy to derive the time
 Now we will examine the amortized time complexity of the individual operations.
 We will show that if we charge $\O(r)$ time against every element inserted, it is enough
 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.
 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.


@@ -380,11 +405,11 @@ and each internal vertex represents a~heap arisen from melding its sons. The lef
 son will be the one with the greater or equal rank. We therefore want to bound
 the sum of ranks of all right sons.
 
 son will be the one with the greater or equal rank. We therefore want to bound
 the sum of ranks of all right sons.
 

-For every right son, we will distribute the change for its rank~$k$ among all leaves
+For every right son, we will distribute the charge for its rank~$k$ among all leaves

 in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same
 rank twice, because the ranks of right sons on every path from the root of the
 tree to a~leaf are strictly decreasing. (This holds because melding of two heaps
 in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same
 rank twice, because the ranks of right sons on every path from the root of the
 tree to a~leaf are strictly decreasing. (This holds because melding of two heaps

-always produces a~heap of a~strictly greater rank.) Hence at most~$n/2^k$
+always produces a~heap of a~rank strictly greater than the smaller of the input ranks.) Hence at most~$n/2^k$

 right sons have rank~$k$ and the total time charged against the leaves is bounded by:
 $$
 \sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n.
 right sons have rank~$k$ and the total time charged against the leaves is bounded by:
 $$
 \sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n.


@@ -400,7 +425,7 @@ of the regular melds.
 Before we estimate the time spent on deletions, we analyse the refills.
 
 \lemma
 Before we estimate the time spent on deletions, we analyse the refills.
 
 \lemma

-Every invokation of the \<Refill> procedure takes time $\O(1)$ amortized.
+Every invocation of \<Refill> takes time $\O(1)$ amortized.

 
 \proof
 When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the
 
 \proof
 When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the


@@ -475,16 +500,18 @@ we can charge the constant time spent on each of them against the operations
 that have created them.
 \qed
 
 that have created them.
 \qed
 

-It remains to take care of the calculation with ranks:
+%%HACK%%
+\>It remains to take care of the calculation with ranks:

 
 \lemma\id{shyards}%
 Every manipulation with ranks performed by the soft heap operations can be
 
 \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
 
 \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
 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.
+the corresponding ``tick'' of the yardstick. We will extend the list whenever necessary.

 
 Comparison of two ranks for equality is then trivial, as is incrementing or decrementing
 the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even
 
 Comparison of two ranks for equality is then trivial, as is incrementing or decrementing
 the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even


@@ -495,15 +522,15 @@ in time proportional to the smaller of them, which is the real cost of the meld
 The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put
 to~$P$ are strictly increasing, we can start walking the list at the rank of the previous
 element in~$P$. The cost is then the difference between the current and the previous rank
 The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put
 to~$P$ are strictly increasing, we can start walking the list at the rank of the previous
 element in~$P$. The cost is then the difference between the current and the previous rank

-and their sum telescopes, again to the real cost of the meld.
+and the sum of these differences telescopes, again to the real cost of the meld.

 \qed
 
 \qed
 

-Now we can put the bits together and laurel our effort with the following theorem:
+We can put the bits together now and laurel our effort with the following theorem:

 
 \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
 
 \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
 heap contains at most $\varepsilon n$ corrupted items.
 
 \proof


@@ -516,13 +543,13 @@ against each \<Insert>. This yields the time bound.
 
 \rem
 When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any
 
 \rem
 When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any

-items, so it can be used like any usual heap. By the standard lower bound on
+items, so it can be used like any traditional heap. By the standard lower bound on

 sorting it therefore requires $\Omega(\log n)$ time per operation, so the
 time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chazelle:softheap}
 proves that it is optimal for every choice of~$\varepsilon$.
 
 The space consumed by the heap need not be linear in the \em{current} number
 sorting it therefore requires $\Omega(\log n)$ time per operation, so the
 time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chazelle:softheap}
 proves that it is optimal for every choice of~$\varepsilon$.
 
 The space consumed by the heap need not be linear in the \em{current} number

-of items, but if a~case where this matters ever occured, we could fix it easily
+of items, but if a~case where this matters ever occurred, we could fix it easily

 by rebuilding the whole data structure completely after $n/2$ deletes. This
 increases the number of potentially corrupted items, but at worst twice, so it
 suffices to decrease~$\varepsilon$ twice.
 by rebuilding the whole data structure completely after $n/2$ deletes. This
 increases the number of potentially corrupted items, but at worst twice, so it
 suffices to decrease~$\varepsilon$ twice.


@@ -532,20 +559,20 @@ suffices to decrease~$\varepsilon$ twice.
 \section{Robust contractions}
 
 Having the soft heaps at hand, we would like to use them in a~conventional MST
 \section{Robust contractions}
 
 Having the soft heaps at hand, we would like to use them in a~conventional MST

-algorithm in place of a~usual heap. The most efficient specimen of a~heap-based
+algorithm in place of a~normal heap. The most efficient specimen of a~heap-based

 algorithm we have seen so far is the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
 It is based on a~simple, yet powerful idea: Run the Jarn\'\i{}k's algorithm with
 algorithm we have seen so far is the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
 It is based on a~simple, yet powerful idea: Run the Jarn\'\i{}k's algorithm with

-limited heap size, so that it stops when the neighborhood of the tree becomes
+limited heap size, so that it stops when the neighborhood of the tree becomes too

 large. Grow multiple such trees, always starting in a~vertex not visited yet. All
 these trees are contained in the MST, so by the Contraction lemma
 (\ref{contlemma}) we can contract each of them to a~single vertex and iterate
 the algorithm on the resulting graph.
 
 large. Grow multiple such trees, always starting in a~vertex not visited yet. All
 these trees are contained in the MST, so by the Contraction lemma
 (\ref{contlemma}) we can contract each of them to a~single vertex and iterate
 the algorithm on the resulting graph.
 

-We can try implanting the soft heap in this algorithm, preferably in the original
+We can try implanting the soft heap in this algorithm, preferably in the earlier

 version without active edges (\ref{jarnik}) as the soft heap lacks the \<Decrease>
 version without active edges (\ref{jarnik}) as the soft heap lacks the \<Decrease>

-operation. This honest, but somewhat simple-minded attempt is however doomed to
+operation. This brave, but somewhat simple-minded attempt is however doomed to

 fail. The reason is of course the corruption of items inside the heap, which
 fail. The reason is of course the corruption of items inside the heap, which

-leads to increase of weights of a~subset of edges. In presence of corrupted
+leads to increase of weights of some subset of edges. In presence of corrupted

 edges, most of the theory we have so carefully built breaks down. For example,
 the Blue lemma (\ref{bluelemma}) now holds only when we consider a~cut with no
 corrupted edges, with a~possible exception of the lightest edge of the cut.
 edges, most of the theory we have so carefully built breaks down. For example,
 the Blue lemma (\ref{bluelemma}) now holds only when we consider a~cut with no
 corrupted edges, with a~possible exception of the lightest edge of the cut.


@@ -555,18 +582,19 @@ the cycle is not corrupted.
 There is fortunately some light in this darkness. While the basic structural
 properties of MST's no longer hold, there is a~weaker form of the Contraction
 lemma that takes the corrupted edges into account. Before we prove this lemma,
 There is fortunately some light in this darkness. While the basic structural
 properties of MST's no longer hold, there is a~weaker form of the Contraction
 lemma that takes the corrupted edges into account. Before we prove this lemma,

-we will expand our awareness of subgraphs which can be contracted.
+we expand our awareness of subgraphs which can be contracted.

 
 \defn
 A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,
 
 \defn
 A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,

-edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints
+of~$G$'s edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints

 of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.
 
 \example\id{jarniscont}%
 Let us see that when we stop the Jarn\'\i{}k's algorithm at some moment and
 we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.
 of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.
 
 \example\id{jarniscont}%
 Let us see that when we stop the Jarn\'\i{}k's algorithm at some moment and
 we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.

-Indeed, when we consider any two distinct edges $uv, xy$ ($u,x\in C$ and $v,y\not\in C$),
-they enter the algorithm's heap at some time. Without loss of generality $uv$~is the first.
+Indeed, when we consider any two distinct edges $uv, xy$ having exactly one endpoint in~$C$
+(w.l.o.g.~$u,x\in C$ and $v,y\not\in C$),
+they enter the algorithm's heap at some time. Without loss of generality $uv$~enters it earlier.

 Before the algorithm reaches the vertex~$x$, it adds the whole path $ux$ to the tree.
 As the edge~$uv$ never leaves the heap, all edges on the path $ux$ must be lighter
 than this edge.
 Before the algorithm reaches the vertex~$x$, it adds the whole path $ux$ to the tree.
 As the edge~$uv$ never leaves the heap, all edges on the path $ux$ must be lighter
 than this edge.


@@ -574,7 +602,7 @@ than this edge.
 We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
 of contractible subgraphs. We again assume that we are working with multigraphs
 and that they need not be connected.
 We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
 of contractible subgraphs. We again assume that we are working with multigraphs
 and that they need not be connected.

-Furthermore, we slightly abuse the notation and we omit the explicit bijection
+Furthermore, we slightly abuse the notation in the way that we omit the explicit bijection

 between $G-C$ and~$G/C$, so we can write $G=C \cup (G/C)$.
 
 \lemman{Generalized contraction}
 between $G-C$ and~$G/C$, so we can write $G=C \cup (G/C)$.
 
 \lemman{Generalized contraction}


@@ -582,77 +610,81 @@ When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(
 
 \proof
 As both sides of the equality are forests spanning the same graph, it suffices
 
 \proof
 As both sides of the equality are forests spanning the same graph, it suffices

-to show that $\msf(G) \subseteq \msf(C)\cup\msf(G/C)$. We know that the edges which
-does not participate in the MSF are exactly those which are the heaviest on some cycle
-(this is the Cycle rule \ref{cyclerule}).
+to show that $\msf(G) \subseteq \msf(C)\cup\msf(G/C)$.
+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 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
 in $\msf(G)$ either.
 
 Similarly for $g\in (G/C)\setminus\msf(G/C)$: when the cycle does not contain
 
 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
 in $\msf(G)$ either.
 
 Similarly for $g\in (G/C)\setminus\msf(G/C)$: when the cycle does not contain

-the vertex~$c$ to which we contracted the subgraph~$C$, the cycle is present
-in~$G$, too. Otherwise we consider the edges $e,f$ adjacent to~$c$ on this cycle.
+the vertex~$c$ to which we have contracted the subgraph~$C$, this cycle is present
+in~$G$, too. Otherwise we consider the edges $e,f$ incident with~$c$ on this cycle.

 Since $C$~is contractible, there must exist a~path~$P$ in~$C$ connecting the endpoints
 of~$e$ and~$f$ in~$G$, such that all edges of~$P$ are lighter than either $e$ or~$f$
 and hence also than~$g$. Expanding~$c$ in the cycle to the path~$P$ then produces
 a~cycle in~$G$ whose heaviest edge is~$g$.
 \qed
 
 Since $C$~is contractible, there must exist a~path~$P$ in~$C$ connecting the endpoints
 of~$e$ and~$f$ in~$G$, such that all edges of~$P$ are lighter than either $e$ or~$f$
 and hence also than~$g$. Expanding~$c$ in the cycle to the path~$P$ then produces
 a~cycle in~$G$ whose heaviest edge is~$g$.
 \qed
 

-We are ready to bring corruption back to the game now and state a~``robust'' version
+We are now ready to bring corruption back to the game and state a~``robust'' version

 of this lemma. A~notation for corrupted graphs will be handy:
 
 \nota\id{corrnota}%
 When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
 R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of
 of this lemma. A~notation for corrupted graphs will be handy:
 
 \nota\id{corrnota}%
 When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
 R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of

-some of the edges in~$R$. As usually, we will assume that all edge weights in this
-graph are pairwise distinct. While this is technically not true for the corruption
-caused by soft heaps, we can easily make the weights unique.
+some of the edges in~$R$. As usually, we will assume that all edges of this graph
+have pairwise distinct weights. While this is technically not true for the corruption
+caused by soft heaps, we can easily make it so.

 
 

-If~$C$ is a~subgraph of~$G$, we will refer to the edges of~$R$ whose exactly
-one endpoint lies in~$C$ by~$R^C$ (i.e., $R^C = R\cap \delta(C)$).
+Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with
+exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$).

 
 

-\lemman{Robust contraction}\id{robcont}%
+\lemman{Robust contraction, Chazelle \cite{chazelle:almostacker}}\id{robcont}%

 Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
 Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$

-for some set of edges~$R$. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.
+for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.

 
 \proof
 We will modify the proof of the previous lemma. We will again consider all possible types
 
 \proof
 We will modify the proof of the previous lemma. We will again consider all possible types

-of edges which do not belong to the right-hand side and show that they are the
+of edges that do not belong to the right-hand side and we will show that they are the

 heaviest edges of certain cycles. Every edge~$g$ of~$G$ lies either in~$C$, or in $H=(G/C)\setminus R^C$,
 or possibly in~$R^C$.
 
 If $g\in C\setminus\msf(C)$, then the same argument as before applies.
 
 heaviest edges of certain cycles. Every edge~$g$ of~$G$ lies either in~$C$, or in $H=(G/C)\setminus R^C$,
 or possibly in~$R^C$.
 
 If $g\in C\setminus\msf(C)$, then the same argument as before applies.
 

-If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $e$~is the heaviest.
-When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are finished.
+If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $g$~is the heaviest.
+When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are done.

 Otherwise we observe that the edges $e,f$ adjacent to~$c$ on this cycle cannot be corrupted
 (they would be in~$R^C$ otherwise, which is impossible). By contractibility of~$C$ there exists
 Otherwise we observe that the edges $e,f$ adjacent to~$c$ on this cycle cannot be corrupted
 (they would be in~$R^C$ otherwise, which is impossible). By contractibility of~$C$ there exists

-a~path~$P$ in~$(G\crpt R)\cup C$ such that all edges of~$P$ are lighter than $e$ or~$f$ and hence
+a~path~$P$ in~$C\crpt (R\cap C)$ such that all edges of~$P$ are lighter than $e$~or~$f$ and hence

 also than~$g$. The weights of the edges of~$P$ in the original graph~$G$ cannot be higher than
 in~$G\crpt R$, so the path~$P$ is lighter than~$g$ even in~$G$ and we can again perform the
 trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst(G)$.
 \qed
 
 \para
 also than~$g$. The weights of the edges of~$P$ in the original graph~$G$ cannot be higher than
 in~$G\crpt R$, so the path~$P$ is lighter than~$g$ even in~$G$ and we can again perform the
 trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst(G)$.
 \qed
 
 \para

-Our plan still is to mimic the Iterative Jarn\'\i{}k's algorithm. We will grow a~collection~$\C$
-of non-overlapping contractible subgraphs and put aside the edges which got corrupted in the process.
-We recursively compute the MSF of the subgraphs and of the contracted graph. Then we take the
+We still intend to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
+of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
+We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the

 union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
 union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce

-the final MSF, but a~sparser graph containing it, on which we can continue.
+the MSF of~$G$, but a~sparser graph containing it, on which we can continue.

 
 

-We can formulate the exact partitioning algorithm as follows:
+%%HACK%%
+\>We can formulate the exact partitioning algorithm and its properties as follows:

 
 

-\algn{Partition a~graph to a~collection of contractible subgraphs}\id{partition}%
+\algn{Partition a~graph to a~collection of contractible clusters}\id{partition}%

 \algo
 \algo

-\algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the subgraphs,
+\algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the clusters,

   and an~accuracy parameter~$\varepsilon$.
 \:Mark all vertices as ``live''.
 \:$\C\=\emptyset$, $R^\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.}
 \:While there is a~live vertex~$v_0$:
   and an~accuracy parameter~$\varepsilon$.
 \:Mark all vertices as ``live''.
 \:$\C\=\emptyset$, $R^\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.}
 \:While there is a~live vertex~$v_0$:

-\::$T=\{v_0\}$. \cmt{the tree we currently grow}
-\::$K=\emptyset$. \cmt{edges known to be corrupted}
-\::\<Create> a~soft heap with accuracy~$\varepsilon$ and \<Insert> the edges adjacent to~$v_0$ in it.
+\::$T=\{v_0\}$. \cmt{the tree that we currently grow}
+\::$K=\emptyset$. \cmt{edges known to be corrupted in the current iteration}
+\::\<Create> a~soft heap with accuracy~$\varepsilon$ and \<Insert> the edges adjacent to~$v_0$ into it.

 \::While the heap is not empty and $\vert T\vert \le t$:
 \:::\<DeleteMin> an~edge $uv$ from the heap, assume $u\in T$.
 \:::If $uv$ was corrupted, add it to~$K$.
 \::While the heap is not empty and $\vert T\vert \le t$:
 \:::\<DeleteMin> an~edge $uv$ from the heap, assume $u\in T$.
 \:::If $uv$ was corrupted, add it to~$K$.


@@ -660,48 +692,53 @@ We can formulate the exact partitioning algorithm as follows:
 \:::$T\=T\cup\{v\}$.
 \:::If $v$ is dead, break out of the current loop.
 \:::Insert all edges incident with~$v$ to the heap.
 \:::$T\=T\cup\{v\}$.
 \:::If $v$ is dead, break out of the current loop.
 \:::Insert all edges incident with~$v$ to the heap.

-\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the subgraph induced by the tree.}
+\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the cluster induced by the tree.}

 \::\<Explode> the heap and add all remaining corrupted edges to~$K$.
 \::\<Explode> the heap and add all remaining corrupted edges to~$K$.

-\::$R^\C\=R^\C \cup \{ K^T \}$. \cmt{Record the ``interesting'' corrupted edges.}
+\::$R^\C\=R^\C \cup K^T$. \cmt{Record the ``interesting'' corrupted edges.}

 \::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.}
 \::Mark all vertices of~$T$ as ``dead''.
 \::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.}
 \::Mark all vertices of~$T$ as ``dead''.

-\algout The collection $\C$ of contractible subgraphs and the set~$R^\C$ of
-corrupted edges in the neighborhood of these subgraphs.
+\algout The collection $\C$ of contractible clusters and the set~$R^\C$ of
+corrupted edges in the neighborhood of these clusters.

 \endalgo
 
 \endalgo
 

-\thmn{Partitioning to contractible subgraphs, Pettie and Ramachandran \cite{pettie:optimal}}\id{partthm}%
+\thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%

 Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
 Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)

-and~$t$, the Partition algorithm \ref{partition} constructs a~collection
-$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges such that:
+and~$t$, the Partition algorithm (\ref{partition}) constructs a~collection
+$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that:

 
 \numlist\ndotted
 
 \numlist\ndotted

-\:All the $C_i$'s and the set~$R^\C$ are edge-disjoint.
-\:Each $C_i$ contains at most~$t$ vertices.
-\:Each vertex of~$G$ is contained in at least one~$C_i$.
-\:The connected components of the union of all $C_i$'s have at least~$t$ vertices each,
-  except perhaps for those which are equal to a~connected component of~$G\setminus R^\C$.
+\:All the clusters and the set~$R^\C$ are mutually edge-disjoint.
+\:Each cluster contains at most~$t$ vertices.
+\:Each vertex of~$G$ is contained in at least one cluster.
+\:The connected components of the union of all clusters have at least~$t$ vertices each,
+  except perhaps for those which are equal to a~connected component of $G\setminus R^\C$.

 \:$\vert R^\C\vert \le 2\varepsilon m$.
 \:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
 \:The algorithm runs in time $\O(n+m\log (1/\varepsilon))$.
 \endlist
 
 \proof
 \:$\vert R^\C\vert \le 2\varepsilon m$.
 \:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
 \:The algorithm runs in time $\O(n+m\log (1/\varepsilon))$.
 \endlist
 
 \proof

-The algorithm grows a~series of trees. A~tree is built from edges adjacent to live vertices
+Claim~1: The Partition algorithm grows a~series of trees which induce the clusters~$C_i$ in~$G$.
+A~tree is built from edges adjacent to live vertices

 and once it is finished, all vertices of the tree die, so no edge is ever reused in another
 and once it is finished, all vertices of the tree die, so no edge is ever reused in another

-tree. Edges of~$R^\C$ are immediately deleted from the graph, so they never participate
-in any tree. The algorithm stops only if all vertices are dead, so each vertex must have
-entered some tree. Each $C_i$ is induced by some tree and the trees have at most~$t$ vertices
-each, which limits the size of the $C_i$'s as well. This proves claims 1--3.
+tree. The edges that enter~$R^\C$ are immediately deleted from the graph, so they never participate
+in any tree.
+
+Claim~2: The algorithm stops when all vertices are dead, so each vertex must have
+entered some tree.
+
+Claim~3: The trees have at most~$t$ vertices each, which limits the size of the
+$C_i$'s as well.

 
 Claim~4: We can show that each connected component has $t$~or more vertices as we already did
 
 Claim~4: We can show that each connected component has $t$~or more vertices as we already did

-in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it already
-has~$t$ vertices, or it joins one of the existing trees (which only increases the
+in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it acquires
+$t$~vertices, or it joins one of the existing trees (this only increases the

 size of the component), or the heap becomes empty (which means that the tree spans
 size of the component), or the heap becomes empty (which means that the tree spans

-a~full component of the current graph and hence also of~$G\setminus R^\C$).
+a~full component of the current graph and hence also of the final~$G\setminus R^\C$).

 
 Claim~5: The set~$R^\C$ contains a~subset of edges corrupted by the soft heaps over
 
 Claim~5: The set~$R^\C$ contains a~subset of edges corrupted by the soft heaps over

-the course of the algorithm. As every edge is inserted to a~heap at most once
-in every direction, the heaps can corrupt at worst $2\varepsilon m$ edges altogether.
+the course of the algorithm. As every edge is inserted to a~heap at most once per
+its endpoint, the heaps can corrupt at worst $2\varepsilon m$ edges altogether.

 
 We will prove the remaining two claims as separate lemmata.
 \qed
 
 We will prove the remaining two claims as separate lemmata.
 \qed


@@ -711,54 +748,54 @@ $$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\biggl( \bigl(G / \bigcup_i C_i
 
 \proof
 By iterating the Robust contraction lemma (\ref{robcont}). Let $K_i$ be the set of edges
 
 \proof
 By iterating the Robust contraction lemma (\ref{robcont}). Let $K_i$ be the set of edges

-corrupted when constructing the subgraph~$C_i$ in the $i$-th phase (iteration of the outer
-loop) of the algorithm, and similarly for the state of the other variables at that time.
+corrupted when constructing the cluster~$C_i$ in the $i$-th phase of the algorithm,
+and similarly for the state of the other variables at that time.

 We will use induction on~$i$ to prove that the lemma holds at the end of every phase.
 
 At the beginning, the statement is obviously true, even as an~equality.
 We will use induction on~$i$ to prove that the lemma holds at the end of every phase.
 
 At the beginning, the statement is obviously true, even as an~equality.

-In the $i$-th phase, we construct the subgraph~$C_j$ by running the partial Jarn\'\i{}k's algorithm on the graph
-$G_i = G\setminus\bigcup_{j<i} K_{\smash j}^{\C_j}$.
-If it were not for corruption, the subgraph~$C_i$ would be contractible, as we already know from Example \ref{jarniscont}.
-When the edges in~$K_i$ get corrupted, the subgraph is contractible in some corrupted graph
+In the $i$-th phase we construct the cluster~$C_i$ by running the partial Jarn\'\i{}k's algorithm on the graph
+$G_i = G\setminus\bigcup_{j<i} K_{\smash j}^{C_j}$.
+If it were not for corruption, the cluster~$C_i$ would be contractible, as we already know from Example \ref{jarniscont}.
+When the edges in~$K_i$ get corrupted, the cluster is contractible in some corrupted graph

 $G_i \crpt K_i$. (We have to be careful as the edges are becoming corrupted gradually,
 $G_i \crpt K_i$. (We have to be careful as the edges are becoming corrupted gradually,

-but it is easy to check that it can only improve the situation.) Since $C_i$~is edge-disjoint
-with the previous trees, it is also a~contractible subgraph of $(G_i / \bigcup_{j<i} C_j) \crpt K_i$.
+but it is easy to check that it can only improve the situation.) Since $C_i$~shares no edges
+with~$C_j$ for any~$j<i$, we know that~$C_i$ also a~contractible subgraph of $(G_i / \bigcup_{j<i} C_j) \crpt K_i$.

 Now we can use the Robust contraction lemma to show that:
 $$
 Now we can use the Robust contraction lemma to show that:
 $$

-\msf\biggl(\bigl(G / \bigcup_{i<j} \bigr) \setminus \bigcup_{i<j} K_j^{\C_j} \biggr) \subseteq
-\msf(C_i) \cup \msf\biggl(\bigl(G / \bigcup_{i\le j} \bigr) \setminus \bigcup_{i\le j} K_j^{\C_j} \biggr) \cup K_i^{C_i},
+\msf\biggl(\bigl(G / \bigcup_{j<i} C_j \bigr) \setminus \bigcup_{j<i} K_j^{C_j} \biggr) \subseteq
+\msf(C_i) \cup \msf\biggl(\bigl(G / \bigcup_{j\le i} C_j \bigr) \setminus \bigcup_{j\le i} K_j^{C_j} \biggr) \cup K_i^{C_i}.

 $$
 $$

-which completes the induction step.
+This completes the induction step, because $K_j^{C_j} = K_j^{\C_j}$ for all~$j$.

 \qed
 
 \lemman{Efficiency of Partition, Claim 7 of Theorem \ref{partthm}}
 The Partition algorithm runs in time $\O(n+m\log(1/\varepsilon))$.
 
 \proof
 \qed
 
 \lemman{Efficiency of Partition, Claim 7 of Theorem \ref{partthm}}
 The Partition algorithm runs in time $\O(n+m\log(1/\varepsilon))$.
 
 \proof

-The inner loop (steps 7--13) processes the edges of the current subgraph~$C_i$ and also
-the edges in its neighborhood $\delta(C_i)$. Steps 6 and~13 insert each such edge to the heap
-at most once, so steps 8--12 also visit each edge at most once. For every edge, we spend
+The inner loop (steps 7--13) processes the edges of the current cluster~$C_i$ and also
+the edges in its neighborhood $\delta(C_i)$. Steps 6 and~13 insert every such edge to the heap
+at most once, so steps 8--12 visit each edge also at most once. For every edge, we spend

 $\O(\log(1/\varepsilon))$ time amortized on inserting it and $\O(1)$ on the other operations
 (by Theorem \ref{softheap} on performance of the soft heaps).
 
 Each edge of~$G$ can participate in some $C_i\cup \delta(C_i)$ only twice before both its
 $\O(\log(1/\varepsilon))$ time amortized on inserting it and $\O(1)$ on the other operations
 (by Theorem \ref{softheap} on performance of the soft heaps).
 
 Each edge of~$G$ can participate in some $C_i\cup \delta(C_i)$ only twice before both its

-ends die. The inner loop therefore processes $\O(m)$ edges total, so we spend $\O(m\log(1/\varepsilon))$
-time there. The rest of the algorithm spends $\O(m)$ time on the other operations with subgraphs
-and $\O(n)$ on identifying the live vertices.
+endpoints die. The inner loop therefore processes $\O(m)$ edges total, so it takes $\O(m\log(1/\varepsilon))$
+time. The remaining parts of the algorithm spend $\O(m)$ time on operations with clusters and corrupted edges
+and additionally $\O(n)$ on identifying the live vertices.

 \qed
 
 %--------------------------------------------------------------------------------
 
 \qed
 
 %--------------------------------------------------------------------------------
 

-\section{Decision trees}
+\section{Decision trees}\id{dtsect}%

 
 The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
 trees constructed by brute force for very small subgraphs. In this section, we will
 explain the basics of the decision trees and prove several lemmata which will
 
 The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
 trees constructed by brute force for very small subgraphs. In this section, we will
 explain the basics of the decision trees and prove several lemmata which will

-turn out to be useful for the analysis of time complexity of the whole algorithm.
+turn out to be useful for the analysis of time complexity of the final algorithm.

 
 

-Let us consider all computations of a~comparison-based MST algorithm when we
+Let us consider all computations of some comparison-based MST algorithm when we

 run it on a~fixed graph~$G$ with all possible permutations of edge weights.
 run it on a~fixed graph~$G$ with all possible permutations of edge weights.

-They can be described by a~tree. The root of the tree corresponds to the first
+The computations can be described by a~binary tree. The root of the tree corresponds to the first

 comparison performed by the algorithm and depending to its result, the computation
 continues either in the left subtree or in the right subtree. There it encounters
 another comparison and so on, until it arrives to a~leaf of the tree where the
 comparison performed by the algorithm and depending to its result, the computation
 continues either in the left subtree or in the right subtree. There it encounters
 another comparison and so on, until it arrives to a~leaf of the tree where the


@@ -768,13 +805,14 @@ Formally, the decision trees are defined as follows:
 
 \defnn{Decision trees and their complexity}\id{decdef}%
 A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
 
 \defnn{Decision trees and their complexity}\id{decdef}%
 A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices

-are labeled with pairs of edges to be compared, each of the two outgoing edges
-corresponds to one possible result of the comparison.\foot{There is no reason
-to compare an~edge with itself and we, as usually, expect that the edge weights are distinct.}
+are labeled with pairs of $G$'s edges to be compared, each of the two outgoing tree edges
+corresponds to one possible result of the comparison.\foot{There are two possible
+outcomes since there is no reason to compare an~edge with itself and we, as usually,
+expect that the edge weights are distinct.}

 Leaves of the tree are labeled with spanning trees of the graph~$G$.
 
 A~\df{computation} of the decision tree on a~specific permutation of edge weights
 Leaves of the tree are labeled with spanning trees of the graph~$G$.
 
 A~\df{computation} of the decision tree on a~specific permutation of edge weights

-in~$G$ is a~path from the root to a~leaf such that the outcome of every comparison
+in~$G$ is the path from the root to a~leaf such that the outcome of every comparison

 agrees with the edge weights. The result of the computation is the spanning tree
 assigned to its final leaf.
 A~decision tree is \df{correct} iff for every permutation the corresponding
 agrees with the edge weights. The result of the computation is the spanning tree
 assigned to its final leaf.
 A~decision tree is \df{correct} iff for every permutation the corresponding


@@ -783,7 +821,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
 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 can 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.
 
 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.


@@ -794,32 +832,32 @@ The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~
 over all graphs~$G$ with $n$~vertices and~$m$ edges.
 
 \obs
 over all graphs~$G$ with $n$~vertices and~$m$ edges.
 
 \obs

-Decision trees are the most general comparison-based computation model possible.
-The only operations which count in the time complexity are the comparisons. All
+Decision trees are the most general deterministic comparison-based computation model possible.
+The only operations that count in its time complexity are comparisons. All

 other computation is free, including solving NP-complete problems or having
 access to an~unlimited source of non-uniform constants. The decision tree
 complexity is therefore an~obvious lower bound on the time complexity of the
 other computation is free, including solving NP-complete problems or having
 access to an~unlimited source of non-uniform constants. The decision tree
 complexity is therefore an~obvious lower bound on the time complexity of the

-problem in all other models.
+problem in all other comparison-based models.

 
 The downside is that we do not know any explicit construction of the optimal
 decision trees, or at least a~non-constructive proof of their complexity.
 On the other hand, the complexity of any existing comparison-based algorithm
 
 The downside is that we do not know any explicit construction of the optimal
 decision trees, or at least a~non-constructive proof of their complexity.
 On the other hand, the complexity of any existing comparison-based algorithm

-can be used as an~upper bound for the decision tree complexity. For example:
+can be used as an~upper bound on the decision tree complexity. For example:

 
 \lemma
 $D(m,n) \le 4/3 \cdot n^2$.
 
 \proof
 
 \lemma
 $D(m,n) \le 4/3 \cdot n^2$.
 
 \proof

-Let us count the comparisons performed by the contractive Bor\o{u}vka's algorithm.
-(\ref{contbor}), tightening up the constants in the original analysis in Theorem
-\ref{contborthm}. In the first phase, each edge participates in two comparisons
-(one for each its endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$
+Let us count the comparisons performed by the Contractive Bor\o{u}vka's algorithm
+(\ref{contbor}), tightening up the constants in its previous analysis in Theorem
+\ref{contborthm}. In the first iteration, each edge participates in two comparisons
+(one per endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$

 comparisons. Then the number of vertices drops at least by a~factor of two, so
 comparisons. Then the number of vertices drops at least by a~factor of two, so

-the subsequent phases spend at most $(n/2)^2, (n/4)^2, \ldots$ comparisons, which sums
-to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$. Between the phases,
+the subsequent iterations spend at most $(n/2)^2, (n/4)^2, \ldots$ comparisons, which sums
+to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$. Between the Bor\o{u}vka steps,

 we flatten the multigraph to a~simple graph, which also needs some comparisons,
 but for every such comparison we remove one of the participating edges, which saves
 we flatten the multigraph to a~simple graph, which also needs some comparisons,
 but for every such comparison we remove one of the participating edges, which saves

-at least one comparison in the subsequent phases.
+at least one comparison in the subsequent steps.

 \qed
 
 \para
 \qed
 
 \para


@@ -828,54 +866,50 @@ show how to find the optimal trees using brute force. The complexity of the sear
 will be of course enormous, but as we already promised, we will need the optimal
 trees only for very small subgraphs.
 
 will be of course enormous, but as we already promised, we will need the optimal
 trees only for very small subgraphs.
 

-\lemman{Construction of optimal decision trees}
-Optimal MST decision trees for all graphs on at most~$k$ vertices can be
-constructed on the Pointer machine in time $\O(2^{2^{4k^2}})$.
+\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}})$.

 
 \proof
 
 \proof

-There are $2^{k\choose 2} \le 2^{k^2}$ undirected graphs on~$k$ vertices. Any
-graph on less than~$k$ vertices can be extended to $k$~vertices by adding isolated
-vertices, which obviously do not affect the optimal decision tree.
-
-For every graph~$G$, we will try all possible decision trees of depth at most $2k^2$
-(we know from the previous lemma that the optimal tree is shallower). We can obtain
+We will try all possible decision trees of depth at most $2n^2$
+(we know from the previous lemma that the desired optimal tree is shallower). We can obtain

 any such tree by taking the complete binary tree of exactly this depth
 any such tree by taking the complete binary tree of exactly this depth

-and labeling its $2\cdot 2^{2k^2}-1$ vertices with comparisons and spanning trees. Those labeled
+and labeling its $2\cdot 2^{2n^2}-1$ vertices with comparisons and spanning trees. Those labeled

 with comparisons become internal vertices of the decision tree, the others
 with comparisons become internal vertices of the decision tree, the others

-become leaves and the parts of the tree below them are cut. There are less
-than $k^4$ possible comparisons and less than $2^{k^2}$ spanning trees of~$G$,
+become leaves and the parts of the tree below them are removed. There are less
+than $n^4$ possible comparisons and less than $2^{n^2}$ spanning trees of~$G$,

 so the number of candidate decision trees is bounded by
 so the number of candidate decision trees is bounded by

-$(k^4+2^{k^2})^{2^{2k^2+1}} \le 2^{(k^2+1)\cdot 2^{2k^2+1}} \le 2^{2^{2k^2+2}} \le 2^{2^{3k^2}}$.
+$(n^4+2^{n^2})^{2^{2n^2+1}} \le 2^{(n^2+1)\cdot 2^{2n^2+1}} \le 2^{2^{2n^2+2}} \le 2^{2^{3n^2}}$.

 
 

-We will enumerate the trees in an~arbitrary order, test each for correctness and
+We will enumerate the trees in an~arbitrary order, test each of them for correctness and

 find the shallowest tree among those correct. Testing can be accomplished by running
 through all possible permutations of edges, each time calculating the MSF using any
 of the known algorithms and comparing it with the result given by the decision tree.
 find the shallowest tree among those correct. Testing can be accomplished by running
 through all possible permutations of edges, each time calculating the MSF using any
 of the known algorithms and comparing it with the result given by the decision tree.

-The number of permutations does not exceed $(k^2)! \le (k^2)^{k^2} \le k^{2k^2} \le 2^{k^3}$
-and each permutation can be checked in time $\O(\poly(k))$.
+The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
+and each one can be checked in time $\O(\poly(n))$.

 
 

-On the Pointer machine, graphs, trees and permutations can be certainly enumerated in time
-$\O(\poly(k))$ per object. The time complexity of the whole algorithm is therefore
-$\O(2^{k^2} \cdot 2^{2^{3k^2}} \cdot 2^{k^3} \cdot \poly(k)) = \O(2^{2^{4k^2}})$.
+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
 
 \qed
 

-\paran{Basic properties of decision trees}
+\paran{Basic properties of decision trees}%

 The following properties will be useful for analysis of algorithms based
 on precomputed decision trees. We will omit some technical details, referring
 The following properties will be useful for analysis of algorithms based
 on precomputed decision trees. We will omit some technical details, referring

-the reader to section 5.1 of the Pettie's paper \cite{pettie:optimal}.
+the reader to section 5.1 of the Pettie's article \cite{pettie:optimal}.

 
 \lemma\id{dtbasic}%
 The decision tree complexity $D(m,n)$ of the MSF satisfies:
 \numlist\ndotted
 \:$D(m,n) \ge m/2$ for $m,n > 2$.
 
 \lemma\id{dtbasic}%
 The decision tree complexity $D(m,n)$ of the MSF satisfies:
 \numlist\ndotted
 \:$D(m,n) \ge m/2$ for $m,n > 2$.

-\:$D(m',n') \ge D(m,n)$ whenever $m'\ge m, n'\ge n$.
+\:$D(m',n') \ge D(m,n)$ whenever $m'\ge m$ and $n'\ge n$.

 \endlist
 
 \proof
 For every $m,n>2$ there is a~graph on $n$~vertices and $m$~edges such that
 every edge lies on a~cycle. Every correct MSF decision tree for this graph
 has to compare each edge at least once. Otherwise the decision tree cannot
 \endlist
 
 \proof
 For every $m,n>2$ there is a~graph on $n$~vertices and $m$~edges such that
 every edge lies on a~cycle. Every correct MSF decision tree for this graph
 has to compare each edge at least once. Otherwise the decision tree cannot

-distinguish between the case when the edge has the lowest of all weights (and
+distinguish between the case when an~edge has the lowest of all weights (and

 thus it is forced to belong to the MSF) and when it has the highest weight (so
 it is forced out of the MSF).
 
 thus it is forced to belong to the MSF) and when it has the highest weight (so
 it is forced out of the MSF).
 


@@ -892,7 +926,7 @@ iff they are edge-disjoint, their union is the whole graph~$G$ and
 $\msf(G) = \bigcup_i \msf(C_i)$ for every permutation of edge weights.
 
 \lemma\id{partiscomp}%
 $\msf(G) = \bigcup_i \msf(C_i)$ for every permutation of edge weights.
 
 \lemma\id{partiscomp}%

-The subgraphs $C_1,\ldots,C_k$ generated by the Partition procedure of the
+The clusters $C_1,\ldots,C_k$ generated by the Partition procedure of the

 previous section (Algorithm \ref{partition}) are compartments of the graph
 $H=\bigcup_i C_i$.
 
 previous section (Algorithm \ref{partition}) are compartments of the graph
 $H=\bigcup_i C_i$.
 


@@ -900,21 +934,21 @@ $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
 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$.
 
 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$.
 

-Let us consider a~cycle $K\subseteq H$ and a~subgraph~$C_i$ such that it contains
-an~edge~$e$ of~$K$ and all subgraphs constructed later by the procedure do not contain
+Let us consider a~cycle $K\subseteq H$ and a~cluster~$C_i$ such that it contains
+an~edge~$e$ of~$K$ and all clusters constructed later by the procedure do not contain

 any. If $K$~is not fully contained in~$C_i$, we can extend the edge~$e$ to a~maximal
 path contained in both~$K$ and~$C_i$. Since $C_i$ shares at most one vertex with the
 any. If $K$~is not fully contained in~$C_i$, we can extend the edge~$e$ to a~maximal
 path contained in both~$K$ and~$C_i$. Since $C_i$ shares at most one vertex with the

-earlier components, there can be at most one edge from~$K$ adjacent to the maximal path,
+earlier clusters, there can be at most one edge from~$K$ adjacent to the maximal path,

 which is impossible.
 \qed
 
 \lemma
 Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then there exists an~optimal
 which is impossible.
 \qed
 
 \lemma
 Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then there exists an~optimal

-MSF decision tree for~$G$ that does not compare edges from distinct compartments.
+MSF decision tree for~$G$ that does not compare edges of distinct compartments.

 
 \proofsketch
 Consider a~subset~$\cal P$ of edge weight permutations~$w$ that satisfy $w(e) < w(f)$
 
 \proofsketch
 Consider a~subset~$\cal P$ of edge weight permutations~$w$ that satisfy $w(e) < w(f)$


@@ -943,19 +977,19 @@ A~collection of decision trees for the individual compartments can be ``glued to
 to a~decision tree for~$G$. We take the decision tree for~$C_1$, replace every its leaf
 by a~copy of the tree for~$C_2$ and so on. Every leaf~$\ell$ of the compound tree will be
 labeled with the union of labels of the original leaves encountered on the path from
 to a~decision tree for~$G$. We take the decision tree for~$C_1$, replace every its leaf
 by a~copy of the tree for~$C_2$ and so on. Every leaf~$\ell$ of the compound tree will be
 labeled with the union of labels of the original leaves encountered on the path from

-the root to the new leaf~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$.
+the root to~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$.

 
 The other inequality requires more effort. We use the previous lemma to transform
 the optimal decision tree for~$G$ to another of the same depth, but without inter-compartment
 comparisons. Then we prove by induction on~$k$ and then on the depth of the tree
 
 The other inequality requires more effort. We use the previous lemma to transform
 the optimal decision tree for~$G$ to another of the same depth, but without inter-compartment
 comparisons. Then we prove by induction on~$k$ and then on the depth of the tree

-that the tree can be re-arranged, so that every computation first compares edges
+that this tree can be re-arranged, so that every computation first compares edges

 from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed
 from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed

-to decision trees for the $C_i$'s and without loss of generality all trees for
-a~single~$C_i$ can be made isomorphic.
+to decision trees for the $C_i$'s. Also, without loss of efficiency all trees for
+a~single~$C_i$ can be made isomorphic to~${\cal D}(C_i)$.

 \qed
 
 \cor\id{dtpart}%
 \qed
 
 \cor\id{dtpart}%

-If $C_1,\ldots,C_k$ are the subgraphs generated by the Partition procedure (Algorithm \ref{partition}),
+If $C_1,\ldots,C_k$ are the clusters generated by the Partition procedure (Algorithm \ref{partition}),

 then $D(\bigcup_i C_i) = \sum_i D(C_i)$.
 
 \proof
 then $D(\bigcup_i C_i) = \sum_i D(C_i)$.
 
 \proof


@@ -975,37 +1009,38 @@ Taking a~maximum over all choices of~$G$ yields $D(2m,2n) \ge \max_G D(G_2) = 2D
 
 %--------------------------------------------------------------------------------
 
 
 %--------------------------------------------------------------------------------
 

-\section{An optimal algorithm}
+\section{An optimal algorithm}\id{optalgsect}%

 
 Once we have developed the soft heaps, partitioning and MST decision trees,
 
 Once we have developed the soft heaps, partitioning and MST decision trees,

-it is now simple to state the Pettie's and Ramachandran's MST algorithm \cite{pettie:optimal}
+it is now simple to state the Pettie's and Ramachandran's MST algorithm

 and prove that it is asymptotically optimal among all MST algorithms in
 comparison-based models. Several standard MST algorithms from the previous
 and prove that it is asymptotically optimal among all MST algorithms in
 comparison-based models. Several standard MST algorithms from the previous

-chapters will play their roles.
+chapters will also play their roles.

 
 We will describe the algorithm as a~recursive procedure. When the procedure is
 
 We will describe the algorithm as a~recursive procedure. When the procedure is

-called on a~graph~$G$, it sets the parameter~$t$ to rougly $\log^{(3)} n$ and
+called on a~graph~$G$, it sets the parameter~$t$ to roughly $\log^{(3)} n$ and

 it calls the \<Partition> procedure to split the graph into a~collection of
 it calls the \<Partition> procedure to split the graph into a~collection of

-subgraphs of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision
-trees to find the MSF of the small subgraphs. The graph obtained by contracting
-the subgraphs is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's
-algorithm runs on it in linear time. Afterwards we combine the MSF's of the subgraphs
+clusters of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision
+trees to find the MSF of the clusters. The graph obtained by contracting
+the clusters is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's
+algorithm runs on it in linear time. Afterwards we combine the MSF's of the clusters

 and of the contracted graphs, we mix in the corrupted edges and run two iterations
 and of the contracted graphs, we mix in the corrupted edges and run two iterations

-of the Contractive Bor\o{u}vka's algorithm. The resulting graph will have both the number of
-vertices and edges reduced by a~constant factor and we recurse on it.
+of the Contractive Bor\o{u}vka's algorithm. This guarantees reduction in the number of
+both vertices and edges by a~constant factor, so we can efficiently recurse on the
+resulting graph.

 
 \algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
 \algo
 \algin A~connected graph~$G$ with an~edge comparison oracle.
 \:If $G$ has no edges, return an~empty tree.
 
 \algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
 \algo
 \algin A~connected graph~$G$ with an~edge comparison oracle.
 \:If $G$ has no edges, return an~empty tree.

-\:$t\=\lceil\log^{(3)} n\rceil$. \cmt{the size of subgraphs}
+\:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}

 \:Call \<Partition> (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
 \:Call \<Partition> (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns

-  a~collection~$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges.
-\:$F_i \= \mst(C_i)$ for all~$i$ obtained using optimal decision trees.
+  a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges.
+\:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees.

 \:$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}
 \:$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$.
   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$.


@@ -1014,35 +1049,44 @@ vertices and edges reduced by a~constant factor and we recurse on it.
 
 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
 
 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:
 $$
 T(m,n) \le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m,
 $$
 
 \lemma\id{optlemma}%
 The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence:
 $$
 T(m,n) \le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m,
 $$

-where~$c_1$ and~$c_2$ are some constants and $D$~is the decision tree complexity
+where~$c_1$ and~$c_2$ are some positive constants and $D$~is the decision tree complexity

 from the previous section.
 
 \proof
 The first two steps of the algorithm are trivial as we have linear time at our
 disposal.
 
 from the previous section.
 
 \proof
 The first two steps of the algorithm are trivial as we have linear time at our
 disposal.
 

-By the Parititioning theorem (\ref{partthm}), the call to \<Partition> with~$\varepsilon$
-set to a~constant takes $\O(m)$ time and it produces a~collection of subgraphs of size
+By the Partitioning theorem (\ref{partthm}), the call to \<Partition> with~$\varepsilon$
+set to a~constant takes $\O(m)$ time and it produces a~collection of clusters of size

 at most~$t$ and at most $m/4$ corrupted edges. It also guarantees that the
 connected components of the union of the $C_i$'s have at least~$t$ vertices
 (unless there is just a~single component).
 
 at most~$t$ and at most $m/4$ corrupted edges. It also guarantees that the
 connected components of the union of the $C_i$'s have at least~$t$ vertices
 (unless there is just a~single component).
 

-\FIXME{Decision trees and sorting}
+To apply the decision trees, we will use the framework of topological computations developed
+in Section \ref{bucketsort}. We pad all clusters in~$\C$ with isolated vertices, so that they
+have exactly~$t$ vertices. We use a~computation that labels the graph with a~pointer to
+its optimal decision tree. Then we apply Theorem \ref{topothm} combined with the
+brute-force construction of optimal decision trees from Lemma \ref{odtconst}. Together they guarantee
+that we can assign the decision trees to the clusters in time:
+$$\O\Bigl(\Vert\C\Vert + t^{t(t+2)} \cdot \bigl(2^{2^{4t^2}} + t^2\bigr)\Bigr)
+= \O\Bigl(m + 2^{2^{2^t}}\Bigr)
+= \O(m).$$
+Execution of the decision tree on each cluster~$C_i$ then takes $\O(D(C_i))$ steps.

 
 The contracted graph~$G_A$ has at most $n/t = \O(n / \log^{(3)}n)$ vertices and asymptotically
 
 The contracted graph~$G_A$ has at most $n/t = \O(n / \log^{(3)}n)$ vertices and asymptotically

-the same number of edges as~$G$, so according to Corollary \ref{ijdens} the Iterated Jarn\'\i{}k's
+the same number of edges as~$G$, so according to Corollary \ref{ijdens}, the Iterated Jarn\'\i{}k's

 algorithm runs on it in linear time.
 
 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
 algorithm runs on it in linear time.
 
 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
 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


@@ -1052,10 +1096,11 @@ The remaining steps of the algorithm can be easily performed in linear time eith
 or in case of the contractions by the bucket-sorting techniques of Section \ref{bucketsort}.
 \qed
 
 or in case of the contractions by the bucket-sorting techniques of Section \ref{bucketsort}.
 \qed
 

-\paran{Optimality}
+\paran{Optimality}%

 The properties of decision tree complexity, which we have proven in the previous
 The properties of decision tree complexity, which we have proven in the previous

-section, will help us show that the time complexity recurrence is satisfied by the
-decision tree complexity $D(m,n)$ itself. This way, we prove the following theorem:
+section, will help us show that the time complexity recurrence is satisfied by a~constant
+multiple of the decision tree complexity $D(m,n)$ itself. This way, we will prove
+the following theorem:

 
 \thmn{Optimality of the Optimal algorithm}
 The time complexity of the Optimal MST algorithm \ref{optimal} is $\Theta(D(m,n))$.
 
 \thmn{Optimality of the Optimal algorithm}
 The time complexity of the Optimal MST algorithm \ref{optimal} is $\Theta(D(m,n))$.


@@ -1069,43 +1114,56 @@ case is trivial, for the induction step we will expand on the previous lemma:
 $$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
 T(m,n)
     &\le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m &(Lemma \ref{optlemma})\cr
 $$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
 T(m,n)
     &\le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m &(Lemma \ref{optlemma})\cr

-    &\le c_1 D(m,n) + T(m/2, n/4) + c_2m &(Corollary \ref{dtpart})\cr
+    &\le c_1 D({\textstyle\bigcup}_i C_i) + T(m/2, n/4) + c_2 m &(Corollary \ref{dtpart})\cr
+    &\le c_1 D(m,n) + T(m/2, n/4) + c_2m &(definition of $D(m,n)$)\cr

     &\le c_1 D(m,n) + cD(m/2, n/4) + c_2m &(induction hypothesis)\cr
     &\le c_1 D(m,n) + c/2\cdot D(m,n/2) + c_2m &(Corollary \ref{dttwice})\cr
     &\le c_1 D(m,n) + c/2\cdot D(m,n) + 2c_2 D(m,n) &(Lemma \ref{dtbasic})\cr
     &\le (c_1 + c/2 + 2c_2) \cdot D(m,n)&\cr
     &\le cD(m,n). &(by setting $c=2c_1+4c_2$)\cr
 }}$$
     &\le c_1 D(m,n) + cD(m/2, n/4) + c_2m &(induction hypothesis)\cr
     &\le c_1 D(m,n) + c/2\cdot D(m,n/2) + c_2m &(Corollary \ref{dttwice})\cr
     &\le c_1 D(m,n) + c/2\cdot D(m,n) + 2c_2 D(m,n) &(Lemma \ref{dtbasic})\cr
     &\le (c_1 + c/2 + 2c_2) \cdot D(m,n)&\cr
     &\le cD(m,n). &(by setting $c=2c_1+4c_2$)\cr
 }}$$

-The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound for
+The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound on

 the time complexity of every comparison-based algorithm.
 \qed
 
 the time complexity of every comparison-based algorithm.
 \qed
 

-\paran{Complexity}
+\paran{Complexity of MST}%

 As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem
 As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem

-is still open and so is therefore the time complexity of the optimal algorithm. However,
+is still open and so therefore is the time complexity of the optimal algorithm. However,

 every time we come up with another comparison-based algorithm, we can use its complexity
 (or more specifically the number of comparisons it performs, which can be even lower)
 every time we come up with another comparison-based algorithm, we can use its complexity
 (or more specifically the number of comparisons it performs, which can be even lower)

-as an~upper bound for the optimal algorithm.
+as an~upper bound on the optimal algorithm.

 
 

-The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$.
+The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$.\foot{$\alpha(m,n)$
+is a~certain inverse of the Ackermann's function, $\lambda_k(n)$ is the row inverse of the same
+function. See \ref{ackerinv} for the exact definitions.}

 It has been discovered by Chazelle \cite{chazelle:ackermann} as an~improvement of his previous
 $\O(m\timesalpha(m,n)\cdot\log\alpha(m,n))$ algorithm \cite{chazelle:almostacker}.
 It has been discovered by Chazelle \cite{chazelle:ackermann} as an~improvement of his previous
 $\O(m\timesalpha(m,n)\cdot\log\alpha(m,n))$ algorithm \cite{chazelle:almostacker}.

-It is also based on the ideas of this section --- in particular the soft heaps and robust contractions.
-The algorithm is unfortunately very complex and it involves a~lot of elaborate
-technical details, so we will only refer to the original paper here. Another algorithm of the same
-complexity, based on similar ideas, has been discovered independently by Pettie \cite{pettie:ackermann}, who,
-having the optimal algorithm at hand, does not take care about the low-level details and only
+It is also based on the ideas of this chapter --- in particular the soft heaps and robust contractions.
+The algorithm is very complex and it involves a~lot of elaborate
+technical details, so we only refer to the original paper here. Another algorithm of the same
+complexity, using similar ideas, has been discovered independently by Pettie \cite{pettie:ackermann}, who,
+having the optimal algorithm at hand, does not take care about the low-level details and he only

 bounds the number of comparisons. Using any of these results, we can prove an~Ackermannian
 upper bound on the optimal algorithm:
 
 bounds the number of comparisons. Using any of these results, we can prove an~Ackermannian
 upper bound on the optimal algorithm:
 

-\thmn{Upper bound on complexity of the Optimal algorithm}
-The time complexity of the Optimal MST algorithm is bounded by $\O(m\timesalpha(m,n))$.
+\thmn{Upper bound on complexity of the Optimal algorithm}\id{optthm}%
+The time complexity of the Optimal MST algorithm is $\O(m\alpha(m,n))$.

 
 \proof
 
 \proof

-Bound $D(m,n)$ by the number of comparisons performed by the algorithms of Chazelle \cite{chazelle:ackermann}
+We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Chazelle \cite{chazelle:ackermann}

 or Pettie \cite{pettie:ackermann}.
 \qed
 
 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\id{lambdacor}%
+The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot \lambda_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$
 \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$


@@ -1113,7 +1171,7 @@ independently on the other edges) or $G_{n,m}$ (we draw the graph uniformly at r
 set of all graphs with~$n$ vertices and $m$~edges), it runs in linear time with high probability,
 regardless of the edge weights.
 
 set of all graphs with~$n$ vertices and $m$~edges), it runs in linear time with high probability,
 regardless of the edge weights.
 

-\paran{Models of computation}
+\paran{Models of computation}%

 Another important consequence of the optimal algorithm is that when we aim for a~linear-time
 MST algorithm (or for proving that it does not exist), we do not need to care about computational
 models at all. The elaborate RAM data structures of Chapter \ref{ramchap}, which have helped us
 Another important consequence of the optimal algorithm is that when we aim for a~linear-time
 MST algorithm (or for proving that it does not exist), we do not need to care about computational
 models at all. The elaborate RAM data structures of Chapter \ref{ramchap}, which have helped us


@@ -1123,12 +1181,10 @@ of oracle. Indeed, whatever trick we employ to achieve linear time complexity, w
 world of decision trees and thus we can use it to show that the algorithm we already knew is
 also linear.
 
 world of decision trees and thus we can use it to show that the algorithm we already knew is
 also linear.
 

-This however applies to deterministic algorithms only --- we already know that access to a~source
-of random bits allows us to compute the MST in expected linear time (the KKT Algorithm, \ref{kkt}).
+This however applies to deterministic algorithms only --- we have shown that access to a~source
+of random bits allows us to compute the MST in expected linear time (the KKT algorithm, \ref{kkt}).

 There were attempts to derandomize the KKT algorithm, but so far the best result in this direction
 is the randomized algorithm also by Pettie \cite{pettie:minirand} which achieves expected linear time
 complexity with only $\O(\log^* n)$ random bits.
 
 There were attempts to derandomize the KKT algorithm, but so far the best result in this direction
 is the randomized algorithm also by Pettie \cite{pettie:minirand} which achieves expected linear time
 complexity with only $\O(\log^* n)$ random bits.
 

-
-

 \endpart
 \endpart