Abstract | We present a parallel priority queue that supports the following operations in
constant time: parallel insertion of a sequence of elements ordered according
to key, parallel decrease key for a sequence of elements ordered according to
key, deletion of the minimum key element, and deletion of an arbitrary element.
Our data structure is the first to support multi-insertion and multi-decrease key in
constant time. The priority queue can be implemented on the EREW PRAM and
can perform any sequence of n operations in O(n) time and O(m log n) work, m
being the total number of keyes inserted and/or updated. A main application is a
parallel implementation of Dijkstra˘s algorithm for the single-source shortest path
problem, which runs in O(n) time and O(m log n) work on a CREW PRAM on
graphs with n vertices and m edges. This is a logarithmic factor improvement in
the running time compared with previous approaches. |