From caf5acc441459f7edd42e0320c07603e18a38e6e Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 8 Mar 2008 22:27:06 +0100
Subject: [PATCH] Finished the verification chapters.

---
 PLAN    |  6 ++++--
 adv.tex | 18 +++++++++++++++---
 2 files changed, 19 insertions(+), 5 deletions(-)

diff --git a/PLAN b/PLAN
index 11d0215..1796580 100644
--- a/PLAN
+++ b/PLAN
@@ -17,8 +17,9 @@
 
   o  Minor-closed classes
   o  Fredman-Tarjan algorithm
-  .  MST verification
-  .  Randomized algorithms
+  o  MST verification
+  o  Linear-time verification
+  .  A randomized algorithm
   .  ?? Chazelle ??
   .  ?? Pettie ??
   o  Special cases and related problems
@@ -65,6 +66,7 @@ Models:
 - mention in-place radix-sorting?
 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
 - add more context from thorup:aczero, also mention FP operations
+- expand the section on radix-sorting, mention Buchsbaum
 
 Ranking:
 
diff --git a/adv.tex b/adv.tex
index 69bdcae..9c4b1ba 100644
--- a/adv.tex
+++ b/adv.tex
@@ -801,7 +801,8 @@ We have proven that $\O(m)$ edge weight comparisons suffice to verify minimality
 of a~given spanning tree. In this section, we will show an~algorithm for the RAM,
 which finds the required comparisons in linear time. We will follow the idea
 of King from \cite{king:verify}, but as we have the power of the RAM data structures
-from Section~\ref{bitsect} at our command, the low-level details will be easier.
+from Section~\ref{bitsect} at our command, the low-level details will be easier,
+especially the construction of vertex and edge labels.
 
 \paran{Reduction}
 First of all, let us make sure that the reduction to fully branching trees
@@ -1029,8 +1030,19 @@ as there are $\O(1)$ query paths per edge, the first sum is $\O(\#\hbox{comparis
 which is $\O(m)$ by Theorem \ref{verify}.
 \qed
 
-\FIXME{Mention online version}
-\FIXME{Mention Buchsbaum}
+\rem
+Buchsbaum et al.~have recently shown in \cite{buchsbaum:verify} that linear-time
+verification can be achieved even on the pointer machine. They first solve the
+problem of finding the lowest common ancestors for a~set of pairs of vertices
+by batch processing, combining an~$\O(m\alpha(m,n))$ algorithm using the Union-Find
+data structure with table lookup for small subtrees. Then they use a~similar
+technique for the path maxima themselves. The tricky part is of course the table
+lookup, which they handle by radix-sorting pointer-based codes of the subtrees.
+
+\rem
+The online version of this problem (build a~data structure for a~weighted tree
+in linear time and then answer queries for individual paths in constant time)
+is still open even for the RAM.
 
 %--------------------------------------------------------------------------------
 
-- 
2.39.2