their values (the values are however never lowered). This allows for
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
-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.
\defnn{Soft heap interface}%
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%%
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
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
Before we estimate the time spent on deletions, we analyse the refills.
\lemma
-Every invocation 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
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
and the sum of these differences telescopes, again to the real cost of the meld.
\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
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
-a~path~$P$ in~$C\crpt (R\cap 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
-We still intend to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
+We still intend to mimic the Iterated 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
the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
-We can formulate the exact partitioning algorithm and its properties as follows:
+%%HACK%%
+\>We can formulate the exact partitioning algorithm and its properties as follows:
\algn{Partition a~graph to a~collection of contractible clusters}\id{partition}%
\algo
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 $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
-and each permutation can be checked in time $\O(\poly(n))$.
+and each one can be checked in time $\O(\poly(n))$.
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
upper bound on the optimal algorithm:
\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))$.
+The time complexity of the Optimal MST algorithm is $\O(m\timesalpha(m,n))$.
\proof
We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Chazelle \cite{chazelle:ackermann}
projects / saga.git / blobdiff