A parallel priority data structure with applications

Presents 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 (1959) algorithm which runs in O(n) time while performing O...

Full description

Saved in:
Bibliographic Details
Main Authors: Brodal, G.S., Traff, J.L., Zaroliagis, C.D.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Computer science
Councils
Data structures
Iterative algorithms
Parallel algorithms
Parallel processing
Phase change random access memory
Shortest path problem
Very large scale integration
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Presents 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 (1959) algorithm which runs in O(n) time while performing O(m log 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.
ISSN:1063-7133
DOI:10.1109/IPPS.1997.580979