research unit 1
 

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

Publication

Type of publication:Article
Entered by:
TitleA Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs
Bibtex cite IDRACTI-RU1-2000-15
Journal Journal of Parallel and Distributed Computing
Year published 2000
Volume 60
Number 9
Pages 1103-1124
Abstract
We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n2=+n1&=) log n) time, performing O(n1+= log n) work for any 0<å<1/2. The strength of the algorithm is its simplicity, making it easy to implement and presumable quite efficient in practice. The algorithm improves upon the work of all previous parallel algorithms. Our algorithm is based on a region decomposition of the input graph and uses a well-known parallel implementation of Dijkstra's algorithm. The logarithmic factor in both the work and the time can be eliminated by plugging in a less practical, sequential planar shortest path algorithm together with an improved parallel implementation of Dijkstra's algorithm.
Authors
Traeff, J.L.
Zaroliagis, Christos
Topics
Top
BibTeXBibTeX
RISRIS
Attachments
J16-JPDC-sp.pdf (main file)
 
Publication ID411