From e0ddb64ea79c2753f51ad2465c87ebfe1a75be4a Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Tue, 4 Mar 2008 17:22:58 +0100
Subject: [PATCH] Mention Thorup's priority queue.

---
 PLAN       |  1 +
 adv.tex    |  7 ++++---
 biblio.bib | 29 ++++++++++++++++++++---------
 3 files changed, 25 insertions(+), 12 deletions(-)

diff --git a/PLAN b/PLAN
index 865e111..91ed33e 100644
--- a/PLAN
+++ b/PLAN
@@ -58,6 +58,7 @@ Spanning trees:
 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
 - parallel algorithms: p243-cole (are there others?)
 - mention 3-regular graphs; bounded expansion?
+- floating-point weights
 
 Models:
 
diff --git a/adv.tex b/adv.tex
index 730e955..0eae4d2 100644
--- a/adv.tex
+++ b/adv.tex
@@ -363,9 +363,10 @@ This is still linear for graphs with density at~least~$n^{1+\varepsilon}$.
 Another possibility is to use the 2-3-heaps \cite{takaoka:twothree} or Trinomial
 heaps \cite{takaoka:trinomial}. Both have the same asymptotic complexity as Fibonacci
 heaps (the latter even in the worst case, but it does not matter here) and their
-authors claim faster implementation.
-
-\FIXME{Mention Thorup's Fibonacci-like heaps for integers?}
+authors claim faster implementation. For integer weights, we can use Thorup's priority
+queues described in \cite{thorup:pqsssp} which have constant-time \<Insert> and \<Decrease>
+and $\O(\log\log n)$ time \<DeleteMin>. (We will however omit the details since we will
+show a~faster integer algorithm soon.)
 
 \para
 As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time
diff --git a/biblio.bib b/biblio.bib
index 7d96bc0..304eb3c 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -296,15 +296,6 @@
   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
 }
 
-@article{ thorup:pq,
-  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
-  author={Thorup, M.},
-  journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
-  pages={149--158},
-  year={2003},
-  publisher={ACM Press New York, NY, USA}
-}
-
 @article{ graham:msthistory,
   title={{On the history of the minimum spanning tree problem}},
   author={Graham, R.L. and Hell, P.},
@@ -881,3 +872,23 @@ inproceedings{ pettie:minirand,
   year={1999},
   publisher={Elsevier}
 }
+
+@article{ thorup:rampq,
+  title={{On RAM priority queues}},
+  author={THORUP, M.},
+  journal={SIAM journal on computing(Print)},
+  volume={30},
+  number={1},
+  pages={86--109},
+  year={2001},
+  publisher={Society for Industrial and Applied Mathematics}
+}
+
+@article{ thorup:pqsssp,
+  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
+  author={Thorup, M.},
+  journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
+  pages={149--158},
+  year={2003},
+  publisher={ACM Press New York, NY, USA}
+}
-- 
2.39.2