From b3579cbf4fc73924d2564856a79865f2bf6f6e2d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 28 Jan 2008 11:43:39 +0100 Subject: [PATCH] Finished iterated Jarnik. --- macros.tex | 1 + mst.tex | 27 ++++++++++++++------------- 2 files changed, 15 insertions(+), 13 deletions(-) diff --git a/macros.tex b/macros.tex index 3fc9efa..7877871 100644 --- a/macros.tex +++ b/macros.tex @@ -32,6 +32,7 @@ \def\<#1>{\leavevmode\hbox{\it #1\/}} \let\>=\noindent \def\qed{{\parfillskip=0pt\allowbreak\hfill\nobreak $\spadesuit$\par}} +\def\qeditem{{\parfillskip=0pt\hfill\rlap{\hskip\rightskip\llap{$\spadesuit$}}\par}} \def\FIXME#1{\>{\bo TODO:} #1} \def\symdiff{\mathbin{\Delta}} \def\hphantas#1#2{\setbox0=\hbox{#2}\hbox to \wd0{#1\hss}} diff --git a/mst.tex b/mst.tex index 64a4921..dadd2a0 100644 --- a/mst.tex +++ b/mst.tex @@ -992,7 +992,7 @@ contract the graph along the edges of~this forest and iterate. \:$m_0\=m$. \:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.} \::$F\=\emptyset$. \cmt{forest built in the current phase} -\::$t\=2^{2m_0/n}$. \cmt{the limit on the heap size} +\::$t\=2^{2m_0/n}$. \cmt{the limit on heap size} \::While there is a~vertex $v_0\not\in F$: \:::Run the improved Jarn\'\i{}k's algorithm (\ref{jarniktwo}) from~$v_0$, stop when: \::::all vertices have been processed, or @@ -1015,26 +1015,26 @@ non-indexed $G$, $m$ and~$n$ will correspond to the graph given as~input. However the choice of the parameter~$t$ can seem mysterious, the following lemma makes the reason clear: -\lemma -The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m_i)$. +\lemma\id{ijphase}% +The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$. \proof During the phase, the heap always contains at most~$t_i$ elements, so it takes time~$\O(\log t_i)=\O(m/n_i)$ to delete an~element from the heap. The trees~$R_i^j$ are disjoint, so there are at most~$n_i$ \'s over the course of the phase. Each edge is considered at most twice (once per its endpoint), so the number -of the other heap operations is~$\O(m_i)$. Together, it equals $\O(m_i + n_i\log t_i) = \O(m_i)$. +of the other heap operations is~$\O(m_i)$. Together, it equals $\O(m_i + n_i\log t_i) = \O(m_i+m) = \O(m)$. \qed \lemma Unless the $i$-th phase is final, the forest~$F_i$ consists of at most $2m_i/t_i$ trees. \proof -As every edge of~$G_i$ is incident with at most two such trees, it is sufficient +As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient to establish that there are at least~$t_i$ edges incident with the vertices of every such tree~(*). -The forest~$F_i$ evolves by additions of the trees~$R_i^j$. There are three possibilities +The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the possibilities how the algorithm could have stopped growing the tree~$R_i^j$: \itemize\ibull \:the heap had more than~$t_i$ elements (step~10): since the elements stored in the heap correspond @@ -1045,9 +1045,8 @@ how the algorithm could have stopped growing the tree~$R_i^j$: instead of edges incident with the tree itself, because we needed the tree edges to be counted as well.} \:all vertices have been processed (step~8): this can happen only in the final phase. +\qeditem \endlist -\>In all three cases, there are sufficiently many incident edges. -\qed \thm\id{itjarthm}% The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time @@ -1064,14 +1063,15 @@ of~$G_{i+1}$ correspond to the components of~$F_i$, by the previous lemma $n_{i+ 2m_i/t_i$. Then $t_{i+1} = 2^{2m/n_{i+1}} \ge 2^{2m/(2m_i/t_i)} = 2^{(m/m_i)\cdot t_i} \ge 2^{t_i}$, therefore: $$ -t_i \ge 2^{2^{2^{\vdots^{m/n}}}} +\left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\vdots^{\scriptstyle m/n}}}} $}}\;\right\} +\,\hbox{a~tower of~$i$ exponentials.} $$ -and as soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time -there is enough space in the heap to process the whole graph. +As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time +there is enough space in the heap to process the whole graph. So~there are +at most~$\beta(m,n)$ phases and we already know (Lemma~\ref{ijphase}) that each +phase runs in linear time. \qed -\FIXME{The notation is clumsy and so is the proof, at least typographically.} - \cor The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$. @@ -1082,6 +1082,7 @@ $\beta(m,n) \le \beta(1,n) = \log^* n$. + % use \para % G has to be connected, so m=O(n) % mention Steiner trees -- 2.39.5