Title :
A linear-processor polylog-time algorithm for shortest paths in planar graphs
Author :
Klein, Philip N. ; Subramanian, Sairam
Author_Institution :
Brown Univ., Providence, RI, USA
Abstract :
We give an algorithm requiring polylog time and a linear number of processors to solve single-source shortest paths in directed planar graphs, bounded-genus graphs, and 2-dimensional overlap graphs. More generally, the algorithm works for any graph provided with a decomposition tree constructed using size-O(√n polylog n) separators
Keywords :
computational geometry; directed graphs; 2-dimensional overlap graphs; bounded-genus graphs; decomposition tree; directed planar graphs; linear-processor polylog-time algorithm; planar graphs; separators; shortest paths; Concurrent computing; Contracts; Parallel algorithms; Particle separators; Transmission line matrix methods; Tree graphs;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366861
