From 2e9f82a6570b037172319c1abe91d32f7d27fb83 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 18 Jan 2008 20:00:39 +0100 Subject: [PATCH] Finish Kruskal. --- biblio.bib | 2 +- macros.tex | 2 +- mst.tex | 46 ++++++++++++++++++++++++++++++++++------------ notation.tex | 1 + 4 files changed, 37 insertions(+), 14 deletions(-) diff --git a/biblio.bib b/biblio.bib index 446a327..02c69e6 100644 --- a/biblio.bib +++ b/biblio.bib @@ -14,7 +14,7 @@ year = "1991", url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" } -@article{ tarjan84setunion, +@article{ tarjan:setunion, author = {Robert E. Tarjan and Jan van Leeuwen}, title = {Worst-case Analysis of Set Union Algorithms}, journal = {J. ACM}, diff --git a/macros.tex b/macros.tex index 9039787..64de0b2 100644 --- a/macros.tex +++ b/macros.tex @@ -32,7 +32,7 @@ \def\<#1>{\leavevmode\hbox{\it #1\/}} \let\>=\noindent \def\qed{{\parfillskip=0pt\allowbreak\hfill\nobreak $\spadesuit$\par}} -\def\FIXME#1{\>{\bo FIXME:} #1} +\def\FIXME#1{\>{\bo TODO:} #1} \def\symdiff{\mathbin{\Delta}} \def\hphantas#1#2{\setbox0=\hbox{#2}\hbox to \wd0{#1\hss}} \def\o#1{\accent23 #1} diff --git a/mst.tex b/mst.tex index bf1df23..5e70a45 100644 --- 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} diff --git a/notation.tex b/notation.tex index 09994e8..c9b7a0f 100644 --- a/notation.tex +++ b/notation.tex @@ -23,6 +23,7 @@ \n{$X \choose k$}{a set of $k$-element subsets of a set~$X$} \n{$G/e$}{multigraph contraction \[contract]} \n{$G.e$}{simple graph contraction \[simpcont]} +\n{$\alpha(n)$}{the inverse Ackermann's function} } \section{Multigraphs and contractions} -- 2.39.5