From 649fd5643221f33883ba9f4f00ef5f9cf415c9db Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 5 Apr 2008 22:00:13 +0200
Subject: [PATCH] Fix references.

---
 macros.tex | 4 ++++
 opt.tex    | 6 +++---
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/macros.tex b/macros.tex
index 850c162..19972c8 100644
--- a/macros.tex
+++ b/macros.tex
@@ -441,6 +441,10 @@
   \vfill\supereject\end
 }
 
+%%% Hyphenation %%%
+
+\hyphenation{Ra-ma-chan-dran}
+
 %%% The End %%%
 
 \catcode`@=12
diff --git a/opt.tex b/opt.tex
index 18e5053..8977d34 100644
--- a/opt.tex
+++ b/opt.tex
@@ -612,7 +612,7 @@ caused by soft heaps, we can easily make the weights unique.
 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)$).
 
-\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$
 for some set of edges~$R$. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.
 
@@ -669,7 +669,7 @@ We can formulate the exact partitioning algorithm as follows:
 corrupted edges in the neighborhood of these subgraphs.
 \endalgo
 
-\thmn{Partitioning to contractible subgraphs, Pettie and Ramachandran \cite{pettie:optimal}}\id{partthm}%
+\thmn{Partitioning to contractible subgraphs, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
 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:
@@ -1080,7 +1080,7 @@ The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound for
 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
 is still open and so is therefore the time complexity of the optimal algorithm. However,
 every time we come up with another comparison-based algorithm, we can use its complexity
-- 
2.39.2