Fixed the definition of edge density in Chapter 3.1.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index e0f4c46d3d5f8cd19205d607501d18426c96ef79..d4bf95284cb8546ded9c9ba0eda197f475c1cdc5 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -328,8 +328,8 @@ and $V\setminus M$ contains no blue edges, therefore we can use the Blue rule.
 
 \nota\id{deltanota}%
 We will use $\delta(M)$ to denote the cut separating~$M$ from its complement.
-That is, $\delta(M) = E \cap (M \times (V\setminus M))$. We will also abbreviate
-$\delta(\{v\})$ as~$\delta(v)$.
+That is, $\delta(M) = \{ uv \in E \mid u\in M, v\not\in M \}$.
+We will also abbreviate $\delta(\{v\})$ as~$\delta(v)$.
 
 \thmn{Red-Blue correctness}%
 For any selection of rules, the Red-Blue procedure stops and the blue edges form
@@ -654,7 +654,7 @@ in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$.
 
 On planar graphs, the algorithm runs much faster:
 
-\thmn{Contractive Bor\o{u}vka on planar graphs}\id{planarbor}%
+\thmn{Contractive Bor\o{u}vka's algorithm on planar graphs, Cheriton and Tarjan \cite{cheriton:mst}}\id{planarbor}%
 When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
 time $\O(n)$.