Finish Kruskal.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index bf1df23e3176e034f3b5e13c34e55812f5fb6153..5e70a45a921fd2a951e48515dc234ae96dd36aab 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -405,17 +405,34 @@ so~$T$ must be the~MST.
 \qed
 
 \impl
-Except for the initial sorting, which in general takes $\O(m\log n)$ time, the only
-other non-trivial operation is detection of cycles. This leads to a well known problem
-of maintaining equivalence classes (disjoint set union), which we will present as ?????
-%%% FIXME: cite
+Except for the initial sorting, which in general takes $\Theta(m\log n)$ time, the only
+other non-trivial operation is detection of cycles. What we need is a data structure
+for maintaining connected components, which supports queries and edge insertion.
+The following theorem shows that it can be done with a surprising efficiency.
+
+\thmn{Incremental connectivity}
+When only edge insertions and queries are allowed, connected components
+can be maintained in $\O(\alpha(n))$ time amortized per operation.
+
+\proof
+Proven by Tarjan and van Leeuwen in \cite{tarjan:setunion}.
+\qed
+
+\FIXME{Define Ackermann's function. Use $\alpha(m,n)$?}
+
+\rem
+The cost of the operations on components is of course dwarfed by the complexity
+of sorting, so a much simpler (at least in terms of its analysis) data
+structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
+per operation. For example, we can label vertices with identifiers of the
+corresponding components and always recolor the smaller of the two components.
 
 \thm
-Kruskal's algorithm finds the MST of the input graph in time $\O(m\log n)$
-or $\O(m\alpha(n))$ if the edges are already sorted.
+Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$
+or $\O(m\alpha(n))$ if the edges are already sorted by their weights.
 
 \proof
-???
+Follows from the above analysis.
 \qed
 
 \section{Contractive algorithms}
@@ -452,11 +469,12 @@ containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
 for~$e$ in~$T$ makes it lighter. \qed
 
 \rem Removal of the heavier of a pair of parallel edges can be also viewed
-as an application of the Red rule on a 2-edge cycle. And indeed it is, the
-Red-Blue procedure works on multigraphs and all the classical algorithms also
-do. We only have to be more careful in the formulations and proofs, which we
-preferred to avoid. We also note that most of the algorithms can be run on
-disconnected graphs with little or no modifications.
+as an application of the Red rule on a two-edge cycle. And indeed it is, the
+Red-Blue procedure works on multigraphs as well as on simple graphs and all the
+classical algorithms also do. We only have to be more careful in the
+formulations and proofs, which we preferred to avoid. We also note that most of
+the algorithms can be run on disconnected graphs with little or no
+modifications.
 
 \algn{Contracting version of Bor\o{u}vka's algorithm}
 \algo
@@ -471,6 +489,10 @@ disconnected graphs with little or no modifications.
 \algout Minimum spanning tree~$T$.
 \endalgo
 
+\FIXME{Show how to do contractions in linear time}
+
+\FIXME{Analyse performance on planar graphs}
+
 \section{Minor-closed graph classes}
 
 \section{Using Fibonacci heaps}