Mention Thorup's priority queue.

[saga.git] / adv.tex

diff --git a/adv.tex b/adv.tex
index 730e955df82bd4af93d49e23b78df3e437a24f36..0eae4d235694800ab3eee2cf088019e896b07180 100644 (file)
--- 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