A Parallel Priority Data Structure with Applications

Gerth Stølting Brodal, Jesper Larsson Träff, and Christos D. Zaroliagis

In Proc. 11th International Parallel Processing Symposium, Dror G. Feitelson and Larry Rudolph (Edt.), pages 689-693, IEEE Comput. Soc. Press, 1997.

Abstract

We present a parallel priority data structure that improves the running time of certain algorithms for problems that lack a fast and work-efficient parallel solution. As a main application, we give a parallel implementation of Dijkstra's algorithm which runs in O(n) time while performing O(mlog n) work on a CREW PRAM . This is a logarithmic factor improvement for the running time compared with previous approaches. The main feature of our data structure is that the operations needed in each iteration of Dijkstra's algorithm can be supported in O(1) time.

Copyright notice

Copyright © 1997 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Online version

ipps97.pdf (208 Kb)

DOI

10.1109/IPPS.1997.580979

BIBT_EX entry

@inproceedings{ipps97,
  author = "Gerth Stølting Brodal and Jesper Larsson Tr{\"a}ff and Christos D. Zaroliagis",
  booktitle = "Proc. 11th International Parallel Processing Symposium",
  doi = "10.1109/IPPS.1997.580979",
  editor = "Dror G. Feitelson and Larry Rudolph",
  isbn = "0-8186-7793-7",
  pages = "689-693",
  publisher = "IEEE Comput. Soc. Press",
  publisheraddress = "Los Alamitos, USA",
  title = "A Parallel Priority Data Structure with Applications",
  year = "1997"
}