From 04d70645d31ed008c97bb20c0b6c2d5fc6ad28a7 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 7 Mar 2008 22:35:22 +0100 Subject: [PATCH] Some more... --- PLAN | 1 + adv.tex | 6 +++++- 2 files changed, 6 insertions(+), 1 deletion(-) diff --git a/PLAN b/PLAN index 40a1092..0bd1e98 100644 --- a/PLAN +++ b/PLAN @@ -57,6 +57,7 @@ Spanning trees: - parallel algorithms: p243-cole (are there others?) - bounded expansion classes? - restricted cases and arborescences +- verify: mention our simplifications Models: diff --git a/adv.tex b/adv.tex index dde5acb..b5c433b 100644 --- a/adv.tex +++ b/adv.tex @@ -783,10 +783,14 @@ of query paths in~$T$ (these are exactly the paths covered by the edges of $G\setminus T$). We use the reduction from Lemma \ref{verbranch} to get an~equivalent problem with a~full branching tree and a~set of parent-descendant paths. Then we run the \ procedure (\ref{findheavy}) to find -the heaviest edges and employ Lemma \ref{vercompares} to bound the number +the heaviest edges and we employ Lemma \ref{vercompares} to bound the number of comparisons used. \qed +\para +We will now show an~efficient implementation of \, which will +run in linear time on the RAM. + -- 2.39.5