From 6d21ffb3141e1b934fbe4895e58b9b977616b245 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 20 Apr 2008 13:51:21 +0200
Subject: [PATCH] Minor improvements.

---
 PLAN       |  4 ++++
 adv.tex    |  6 +++---
 biblio.bib | 11 +++++++++++
 3 files changed, 18 insertions(+), 3 deletions(-)

diff --git a/PLAN b/PLAN
index 643251f..41930d0 100644
--- a/PLAN
+++ b/PLAN
@@ -101,3 +101,7 @@ Global:
 
 - each chapter should make clear in which model we work
 - clean up bibliography
+
+Pictures:
+
+- structure of a Q-heap
diff --git a/adv.tex b/adv.tex
index f9e0938..f9f7f87 100644
--- a/adv.tex
+++ b/adv.tex
@@ -1032,7 +1032,7 @@ 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
 
-\rem\id{pmverify}%
+\paran{Verification on the Pointer Machine}\id{pmverify}%
 Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown 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
@@ -1041,7 +1041,7 @@ based on the Disjoint Set Union data structure with the framework of topological
 computations developed in Section \ref{bucketsort}. Then they use a~similar
 technique for finding the peaks themselves.
 
-\rem
+\paran{Online verification}%
 The online version of this problem has turned out to be more difficult. It calls for an~algorithm
 that preprocesses the tree and then answers queries for peaks of paths presented online. Pettie
 \cite{pettie:onlineverify} has proven an~interesting lower bound based on the inverses of the
@@ -1245,7 +1245,7 @@ requires an~unbounded number of random bits in the worst case.
 
 \rem
 The only place where we needed the power of the RAM is finding the heavy edges,
-so we can employ the pointer-machine verification algorithm mentioned in Remark \ref{pmverify}
+so we can employ the pointer-machine verification algorithm mentioned in \ref{pmverify}
 to bring the results of this section to the~PM.
 
 %--------------------------------------------------------------------------------
diff --git a/biblio.bib b/biblio.bib
index 3dead5b..cb317ab 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -1483,3 +1483,14 @@
   year={1992},
   publisher={Oxford University Press}
 }
+
+@article{ katoh:kmin,
+  author = {N. Katoh and T. Ibaraki and H. Mine},
+  title = {An Algorithm for Finding $K$ Minimum Spanning Trees},
+  publisher = {SIAM},
+  year = {1981},
+  journal = {SIAM Journal on Computing},
+  volume = {10},
+  number = {2},
+  pages = {247--255},
+}
-- 
2.39.5