Efficient parallel algorithms for shortest paths in planar digraphs
From MaRDI portal
Publication:1196454
DOI10.1007/BF01994878zbMath0761.68047MaRDI QIDQ1196454
Christos D. Zaroliagis, Grammati E. Pantziou, Paul G. Spirakis
Publication date: 14 December 1992
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01994878
shortest path; CREW PRAM; compact routing tables; planar digraph; hammock-decomposition technique; outerplanar digraph; parallel tree contraction
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W15: Distributed algorithms
Related Items
Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, A Glimpse at Paul G. Spirakis
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Optimal parallel algorithms on planar graphs
- Designing networks with compact routing tables
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- On the Complexity of Covering Vertices by Faces in a Planar Graph
- Parallel Matrix and Graph Algorithms
- New Bounds on the Complexity of the Shortest Path Problem
- Planar graph decomposition and all pairs shortest paths
- A simple parallel tree contraction algorithm