BUGS: Little ones to fix

[saga.git] / abstract.tex

diff --git a/abstract.tex b/abstract.tex
index c05f657ee5f8f4db9766b35457642bc337e4466d..7c679367e862fd2b946f3f086d7cd9f8c3788616 100644 (file)
--- a/abstract.tex
+++ b/abstract.tex
@@ -6,7 +6,6 @@
 \advance\hsize by 1cm
 \advance\vsize by 20pt
 
-\font\chapfont=csb14 at 16pt
 \def\rawchapter#1{\vensure{0.5in}\bigskip\goodbreak
 \leftline{\chapfont #1}
 }
@@ -210,8 +209,8 @@ and also to analyse:
 \endalgo
 
 \thm
-The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
-time $\O(\min(n^2,m\log n))$.
+The Contractive Bor\o{u}vka's algorithm finds the MST of the graph given as
+its input in time $\O(\min(n^2,m\log n))$.
 
 We also show that this time bound is tight --- we construct an~explicit
 family of graphs on which the algorithm spends $\Theta(m\log n)$ steps.
@@ -671,6 +670,7 @@ of non-overlapping contractible subgraphs called \df{clusters} and we put aside
 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.
+%%The following theorem describes the properties of this partition:
 
 \thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
 Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
@@ -691,7 +691,8 @@ and~$t$, we can construct a~collection $\C=\{C_1,\ldots,C_k\}$ of clusters and a
 
 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.
-Formally, the decision trees are defined as follows:
+%%Formally, the decision trees are defined as follows:
+Let us define them first:
 
 \defnn{Decision trees and their complexity}\id{decdef}%
 A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
@@ -755,7 +756,7 @@ We will describe the algorithm as a~recursive procedure:
   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}).
+\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (see Section \ref{iteralg}).
 \:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
 \: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.