MPI-I-96-1-012

A simple parallel algorithm for the single-source shortest path problem on planar diagraphs

Träff, Jesper L. and Zaroliagis, Christos D.

MPI-I-96-1-012. June 1996, 17 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We present a simple parallel algorithm for the {\em single-source shortest path problem} in {\em planar digraphs} with nonnegative real edge weights.
The algorithm runs on the EREW PRAM model of parallel computation in $O((n^{2\epsilon} + n^{1-\epsilon})\log n)$ time, performing
$O(n^{1+\epsilon}\log n)$ work for any $0<\epsilon<1/2$. The strength of the algorithm is its simplicity, making it easy to implement, and presumably 474 quite efficient in practice.
The algorithm improves upon the work of all previous algorithms.
The work can be further reduced to $O(n^{1+\epsilon})$, by plugging in a less practical, sequential planar shortest path
algorithm.
Our algorithm is based on a region decomposition of the input graph, and uses a well-known parallel implementation of Dijkstra's algorithm.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	281 KBytes; 291 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-012

BibTeX
@TECHREPORT{TräffZaroliagis96, AUTHOR = {Tr{\"a}ff, Jesper L. and Zaroliagis, Christos D.}, TITLE = {A simple parallel algorithm for the single-source shortest path problem on planar diagraphs}, TYPE = {Research Report}, INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik}, ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany}, NUMBER = {MPI-I-96-1-012}, MONTH = {June}, YEAR = {1996}, ISSN = {0946-011X},}