From 0416ec8524278edf87359017ce76fe6c9a7c7659 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 17 Mar 2008 17:44:29 +0100 Subject: [PATCH] Improve analysis of contractive Boruvka. --- mst.tex | 53 +++++++++++++++++++++++++++++------------------------ 1 file changed, 29 insertions(+), 24 deletions(-) diff --git a/mst.tex b/mst.tex index b79d0c8..6e6310b 100644 --- a/mst.tex +++ b/mst.tex @@ -520,35 +520,50 @@ formulations and proofs, which we preferred to avoid. \:$T\=\emptyset$. \:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.} \:While $n(G)>1$: -\::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$. -\::$T\=T\cup \{ \ell(e_i) \}$. \cmt{Remember labels of all selected edges.} -\::Contract $G$ along all edges $e_i$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.} +\::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$. +\::$T\=T\cup \{ \ell(e_k) \}$. \cmt{Remember labels of all selected edges.} +\::Contract $G$ along all edges $e_k$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.} \::Flatten $G$, removing parallel edges and loops. \algout Minimum spanning tree~$T$. \endalgo +\nota +For the analysis of the algorithm, we will denote the graph considered by the algorithm +at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and the number +of vertices and edges of this graph by $n_i$ and $m_i$ respectively. + \lemma\id{contiter}% -Each iteration of the algorithm can be carried out in time~$\O(m)$. +The $i$-th iteration of the algorithm (also called the Bor\o{u}vka step) can be carried +out in time~$\O(m_i)$. \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 \ref{boruvkaiter}): -We build an auxillary graph containing only the selected edges~$e_i$, find +We build an auxillary graph containing only the selected edges~$e_k$, find connected components of this graph and renumber vertices in each component to -the identifier of the component. This takes $\O(m)$ time. +the identifier of the component. This takes $\O(m_i)$ 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)$. +$\O(n_i+m_i)=\O(m)$. \qed \thm -The Contractive Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$. +The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in +time $\O(\min(n^2,m\log n))$. \proof As in the original Bor\o{u}vka's algorithm, the number of iterations is $\O(\log n)$. -Then apply the previous lemma. +When combined with the previous lemma, it gives an~$\O(m\log n)$ upper bound. + +To get the $\O(n^2)$ bound, we observe that the number of trees in the non-contracting +version of the algorithm drops at least by a factor of two in each iteration (Lemma \ref{boruvkadrop}) +and the same must hold for the number of vertices in the contracting version. +Therefore $n_i\le n/2^i$. While the number of edges need not decrease geometrically, +we still have $m_i\le n_i^2$ as the graphs~$G_i$ are simple (we explicitly removed multiple +edges and loops at the end of the previous iteration). Hence the total time spent +in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$. \qed \thmn{Contractive Bor\o{u}vka on planar graphs, \cite{mm:mst}}\id{planarbor}% @@ -556,22 +571,12 @@ When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in time $\O(n)$. \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 geometrically. - -The number of trees in the non-contracting version of the algorithm drops -at least by a factor of two in each iteration (Lemma \ref{boruvkadrop}) and the -same must hold for the number of vertices in the contracting version. -Therefore $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. Hence we can use the standard theorem on +Let us refine the previous proof. We already know that $n_i \le n/2^i$. We will +prove that when~$G$ is planar, the $m_i$'s are decreasing geometrically. We know that every +$G_i$ is planar, because the class of planar graphs is closed under edge deletion and +contraction. Moreover, $G_i$~is also simple, 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(\sum_i n/2^i)=\O(n)$. +The total time complexity of the algorithm is therefore $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$. \qed \rem -- 2.39.2