From f8fcc3700c80471ec8578cf4b77f47230947ab8d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 22 Feb 2008 18:13:07 +0100 Subject: [PATCH] Fix proof of the local contractive algorithm. --- PLAN | 2 -- adv.tex | 9 +++++---- 2 files changed, 5 insertions(+), 6 deletions(-) diff --git a/PLAN b/PLAN index 8039758..a397476 100644 --- a/PLAN +++ b/PLAN @@ -45,8 +45,6 @@ TODO: Spanning trees: -- prove the density bound -- fix proof of the local contraction alg - cite Eisner's tutorial \cite{eisner:tutorial} - \cite{pettie:onlineverify} online lower bound - mention Steiner trees diff --git a/adv.tex b/adv.tex index f4dc358..bf78611 100644 --- a/adv.tex +++ b/adv.tex @@ -194,10 +194,11 @@ of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s are minors of the graph~$G$ given as the input. For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg}) -guarantees that at least $n_i/2$ edges get selected in the $i$-th iteration. -Hence at least a half of the vertices participates in contractions, so -$n_i\le 3/4\cdot n_{i-1}$. Therefore $n_i\le n\cdot (3/4)^i$ and the algorithm terminates -after $\O(\log n)$ iterations. +guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices +have degree at most~$t$. Each selected edge removes one such vertex and +possibly increases the degree of another, so at least $n_i/4$ edges get selected. +Hence $n_i\le 3/4\cdot n_{i-1}$ and therefore $n_i\le n\cdot (3/4)^i$ and the +algorithm terminates after $\O(\log n)$ iterations. Each selected edge belongs to $\mst(G)$, because it is the lightest edge of the trivial cut $\delta(v)$ (see the Blue Rule in \ref{rbma}). -- 2.39.2