From aa8c33c5535bde5f26cec0052d04a5dc91f87952 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Jan 2008 20:02:17 +0100 Subject: [PATCH] Contractions. --- biblio.bib | 10 ++++++ macros.tex | 2 ++ mst.tex | 93 ++++++++++++++++++++++++++++++++++++++++++++++++---- notation.tex | 6 ++-- 4 files changed, 102 insertions(+), 9 deletions(-) diff --git a/biblio.bib b/biblio.bib index 02c69e6..e20ad33 100644 --- a/biblio.bib +++ b/biblio.bib @@ -341,3 +341,13 @@ publisher={Wiley, New York}, year={1965} } + +@article{ boyer:cutting, + title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}}, + author={Boyer, J.M. and Myrvold, W.J.}, + journal={Journal of Graph Algorithms and Applications}, + volume={8}, + number={3}, + pages={241--273}, + year={2004} +} diff --git a/macros.tex b/macros.tex index 64de0b2..52b30c5 100644 --- a/macros.tex +++ b/macros.tex @@ -36,6 +36,7 @@ \def\symdiff{\mathbin{\Delta}} \def\hphantas#1#2{\setbox0=\hbox{#2}\hbox to \wd0{#1\hss}} \def\o#1{\accent23 #1} +\def\mst{{\rm mst}} % Footnotes \newcount\footcnt @@ -300,6 +301,7 @@ \def\alg{\proclaim{Algorithm}} \def\impl{\proclaim{Implementation}} \def\cor{\proclaim{Corollary}} +\def\nota{\proclaim{Notation}} \def\label#1{{\sl (#1)\/}\enspace} diff --git a/mst.tex b/mst.tex index 5e70a45..354e0d6 100644 --- a/mst.tex +++ b/mst.tex @@ -187,6 +187,10 @@ minimum spanning trees, the unique MST of the new graph will still be a MST of t original graph. In the few cases where we need a more concrete input, we will explicitly state so. +\nota\thmid{mstnota}% +When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote +its unique minimum spanning tree. + \section{The Red-Blue Meta-Algorithm} Most MST algorithms can be described as special cases of the following procedure @@ -209,7 +213,7 @@ the procedure always stops and gives the correct result. Also, it will turn out that each of the classical MST algorithms can be described as a specific way of choosing the rules in this procedure, which justifies the name meta-algorithm. -\proclaim{Notation}% +\nota We will denote the unique minimum spanning tree of the input graph by~$T_{min}$. We intend to prove that this is also the output of the procedure. @@ -307,7 +311,7 @@ of the cycle). Then $e_2=v_2u_3$ and $w(e_2)w which is a contradiction. (Note that distinctness of edge weights was crucial here.) \qed -\lemma +\lemma\thmid{boruvkadrop}% In each iteration of the algorithm, the number of trees in~$T$ drops at least twice. \proof @@ -318,7 +322,7 @@ consists of at least two original trees. \cor The algorithm stops in $\O(\log n)$ iterations. -\lemma +\lemma\thmid{boruvkaiter}% Each iteration can be carried out in time $\O(m)$. \proof @@ -471,9 +475,9 @@ 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 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 +classical algorithms also do. We only would 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 +the algorithms can be run on disconnected multigraphs with little or no modifications. \algn{Contracting version of Bor\o{u}vka's algorithm} @@ -489,9 +493,84 @@ modifications. \algout Minimum spanning tree~$T$. \endalgo -\FIXME{Show how to do contractions in linear time} +\lemma +Each iteration of the algorithm can be carried out in time~$\O(m)$. + +\proof +The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly +to the unions in the original Bor\o{u}vka's algorithm (see \thmref{boruvkaiter}). +We build an auxillary graph containing only the selected edges~$e_i$, find +connected components of this graph and renumber vertices in each component to +the identifier of the component. This takes $\O(m)$ time. + +Flattening is performed by first removing the loops and then bucket-sorting the edges +(as ordered pairs of vertex identifiers) lexicographically, which brings parallel +edges together. The bucket sort uses two passes with $n$~buckets, so it takes +$\O(n+m)=\O(m)$. +\qed + +\thm +The Contracting Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$. + +\proof +As in the original Bor\o{u}vka's algorithm, the number of phases is $\O(\log n)$. +Then apply the previous lemma. +\qed + +\thmn{\cite{mm:mst}} +When the input graph is planar, the Contracting Bor\o{u}vka's algorithm runs in +time $\O(m)$. + +\proof +Let us denote the graph considered by the algorithm at the beginning of the $i$-th +iteration by $G_i$ (starting with $G_0=G$) and its number of vertices and edges +by $n_i$ and $m_i$ respectively. As we already know from the previous lemma, +the $i$-th iteration takes $\O(m_i)$ time. We are going to prove that the +$m_i$'s are decreasing exponentially. + +The number of trees in the non-contracting version of the algorithm decreases +at least twice in each iteration (Lemma \thmref{boruvkadrop}) and therefore the +same must hold for the number of vertices in the contracting version. So $n_i\le n/2^i$. + +However, every $G_i$ is planar, because the class of planar graphs is closed +under edge deletion and contraction. The~$G_i$ is also simple as we explicitly removed multiple edges and +loops at the end of the previous iteration. So we can use the standard theorem on +the number of edges of planar simple graphs (see for example \cite{diestel:gt}) to get $m_i\le 3n_i \le 3n/2^i$. +From this we get that the total time complexity is $\O(\sum_i m_i)=\O(m)$. +\qed + +\rem +There are other possibilities how to find the MST of a planar graph in linear time. +Matsui \cite{matsui:planar} has described an algorithm based on simultaneously +processing the graph and its dual. The advantage of our approach is that we do not +need to construct the planar embedding first. + +\rem +To achieve the linear time complexity, the algorithm needs a very careful implementation. +Specifically, when we represent the graph using adjacency lists, whose heads are stored +in an array indexed by vertex identifiers, we must renumber the vertices in each iteration. +Otherwise, unused identifiers could end up taking most of space in the arrays and scans of these +arrays would have super-linear cost with respect to the size of the current graph~$G_i$. + +\rem +The algorithm can be also implemented on the pointer machine. Representation of graphs +by pointer structures easily avoids the aforementioned problems with sparse arrays, +but we need to handle the bucket sorting somehow. We can create a small data structure +for every vertex and use a pointer to this structure as a unique identifier of the vertex. +We will also keep a list of all vertex structures. During the bucket sort, each vertex +structure will contain a pointer to the corresponding bucket and the vertex list will +define the order of vertices (which can be arbitrary, but has to be fixed). + +Graph contractions are a very powerful tool and they can be used in other MST +algorithms as well. The following lemma shows the gist: + +\lemman{Contraction of MST edges} +Let $G$ be a weighted multigraph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph +produced by contracting $G$ along~$e$ and $\pi$ the bijection between edges of~$G-e$, and +their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$ -\FIXME{Analyse performance on planar graphs} +\proof +\qed \section{Minor-closed graph classes} diff --git a/notation.tex b/notation.tex index c9b7a0f..cd7f8dd 100644 --- a/notation.tex +++ b/notation.tex @@ -18,12 +18,14 @@ \n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$} \n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$} \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm} -\n{MST}{minimal spanning tree \[mstdef]} -\n{MSF}{minimal spanning forest \[mstdef]} +\n{MST}{minimum spanning tree \[mstdef]} +\n{MSF}{minimum spanning forest \[mstdef]} +\n{\mst(G)}{the unique minimum spanning tree of a graph~$G$ \[mstnota]} \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} +\n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$.} } \section{Multigraphs and contractions} -- 2.39.2