Corrected bugs reported by Koubek.

[saga.git] / opt.tex

diff --git a/opt.tex b/opt.tex
index bf30371d6fc71f2c75059b7369f056f78e8bad3d..067ac93a268cc556e548fbb371b596b71acba4d7 100644 (file)
--- a/opt.tex
+++ b/opt.tex
@@ -666,7 +666,7 @@ trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst
 \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
@@ -1147,7 +1147,7 @@ bounds the number of comparisons. Using any of these results, we can prove an~Ac
 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}