Details

Autor(en) / Beteiligte

• Brodal, G.S.
• Traff, J.L.
• Zaroliagis, C.D.

Titel

A parallel priority data structure with applications

Ist Teil von

• Proceedings - International Parallel Processing Symposium, 1997, p.689-693

Ort / Verlag

IEEE

Erscheinungsjahr

1997

Link zum Volltext

• IEEE_Xplore

Quelle

IEEE Electronic Library (IEL)

Beschreibungen/Notizen

• 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.