In the definiton of the soft queue, we should better explicitly mention that

[saga.git] / adv.tex

diff --git a/adv.tex b/adv.tex
index d56f58cce16bb5a19a70841b9023f8f49f4b4b9d..2a81be339ee37a25dc2d122741ec139154d641b4 100644 (file)
--- a/adv.tex
+++ b/adv.tex
@@ -8,7 +8,7 @@
 
 The contractive algorithm given in Section~\ref{contalg} has been found to perform
 well on planar graphs, but in the general case its time complexity was not linear.
-Can we find any broader class of graphs where this algorithm is still efficient?
+Can we find any broader class of graphs where this algorithm is still linear?
 The right context turns out to be the minor-closed graph classes, which are
 closed under contractions and have bounded density.
 
@@ -57,12 +57,11 @@ guarantees that we can always find a~finite set of forbidden minors:
 \thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
 For every non-trivial minor-closed graph class~$\cal C$ there exists
 a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$.
+\qed
 
-\proof
 This theorem has been proven in a~long series of papers on graph minors
 culminating with~\cite{rs:wagner}. See this paper and follow the references
 to the previous articles in the series.
-\qed
 
 \para
 For analysis of the contractive algorithm,
@@ -126,7 +125,7 @@ $G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor.
 
 Let us return to the analysis of our algorithm.
 
-\thmn{MST on minor-closed classes, Mare\v{s} \cite{mm:mst}}\id{mstmcc}%
+\thmn{MST on minor-closed classes, Tarjan \cite{tarjan:dsna}}\id{mstmcc}%
 For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
 algorithm (\ref{contbor}) finds the MST of any graph of this class in time
 $\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
@@ -257,8 +256,8 @@ has degree~9.
 \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
 
 \rem
-The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt \cite{gustedt:parallel},
-who studied a~parallel version of the Contractive Bor\o{u}vka's algorithm applied
+The observation in~Theorem~\ref{mstmcc} was also used by Gustedt \cite{gustedt:parallel},
+to construct parallel version of the Contractive Bor\o{u}vka's algorithm applied
 to minor-closed classes.
 
 \rem
@@ -420,7 +419,7 @@ contract the edges of~this forest and iterate.
 \algin A~graph~$G$ with an edge comparison oracle.
 \:$T\=\emptyset$. \cmt{edges of the MST}
 \:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
-\:$m_0\=m$.
+\:$m_0\=m$. \cmt{in the following, $n$ and $m$ will change with the graph}
 \:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
 \::$F\=\emptyset$. \cmt{forest built in the current phase}
 \::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
@@ -505,7 +504,7 @@ time (Lemma~\ref{ijphase}).
 The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
 
 \proof
-$\beta(m,n) \le \beta(1,n) \le \log^* n$.
+$\beta(m,n) \le \beta(n,n) \le \log^* n$.
 \qed
 
 \cor\id{ijdens}%
@@ -1128,8 +1127,8 @@ The number of $F$-nonheavy edges is therefore equal to the total number of the c
 flips in step~2 of this algorithm. We also know that the algorithm stops before
 it adds $n$~edges to~$F$. Therefore it flips at most as many coins as a~simple
 random process that repeatedly flips until it gets~$n$ heads. As waiting for
-every occurrence of heads takes expected time~$1/p$, waiting for~$n$ heads
-must take $n/p$. This is the bound we wanted to achieve.
+every occurrence of heads takes expected time~$1/p$ (the distribution is geometric),
+waiting for~$n$ heads must take $n/p$. This is the bound we wanted to achieve.
 \qed
 
 \para