Efficient parallel algorithms for shortest paths in planar digraphs

DOI10.1007/BF01994878zbMath0761.68047MaRDI QIDQ1196454

Paul G. Spirakis, Christos D. Zaroliagis, Grammati E. Pantziou

Publication date: 14 December 1992

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

shortest path; CREW PRAM; compact routing tables; planar digraph; hammock-decomposition technique; outerplanar digraph; parallel tree contraction

Mathematics Subject Classification ID

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, A Glimpse at Paul G. Spirakis

Uses Software

• Algorithm 97

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