A linear-processor polylog-time algorithm for shortest paths in planar graphs

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(/spl radic/n polylog n) separators. >

Authors

• Philip N. Klein
• Sairam Subramanian

Keywords

• Particle separators
• Contracts
• Tree graphs
• Transmission line matrix methods
• Concurrent computing
• Parallel algorithms
• Shortest Path
• Linear Graph
• Planar Graphs
• Shortest Paths In The Graph
• Joining Tree
• Number Of Processors
• Path Length
• Use Of Algorithms
• Estimation Problem
• Pathfinding
• Distance Estimation
• Recursive Algorithm
• Scaling Algorithm
• Original Graph
• Breadth-first Search
• Graph Metrics
• Approximate Distance
• Sparse Graph
• Input Graph
• Shortest Path Problem
• Exact Distance
• Shortest Path Distance
• Split Set
• Exact Problem
• Running Time