research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleA Parallel Priority Queue with Constant Time Operations
Bibtex cite IDRACTI-RU1-1998-6
Journal Parallel and Distributed Computing
Year published 1998
Volume 49
Number 1
Pages 4-21
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.
Brodal, Gerth Stolting
Traff, Jesper Larsson
Zaroliagis, Christos
A parallel priority queue.pdf (main file)
Publication ID858