Fixed the definition of edge density in Chapter 3.1.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 8a6a12a278b66ac23924bcbcf551e06a618ee5fb..d4bf95284cb8546ded9c9ba0eda197f475c1cdc5 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -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)$.