Efficient parallel algorithms for shortest paths in planar digraphs

DOI10.1007/BF01994878zbMath0761.68047OpenAlexW1971715758MaRDI 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

zbMATH Keywords

shortest pathCREW PRAMcompact routing tablesplanar digraphhammock-decomposition techniqueouterplanar digraphparallel tree contraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (3)

Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ A Glimpse at Paul G. Spirakis ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems

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

This page was built for publication: Efficient parallel algorithms for shortest paths in planar digraphs