Efficient parallel algorithms for shortest paths in planar graphs

DOI10.1007/3-540-52846-6_98MaRDI QIDQ5056111zbMATH OpenOpenAlexFDO

Authors Grammati Pantziou, P. G. Spirakis, Christos Zaroliagis

Publication date 9 December 2022

Published in SWAT 90 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52846-6_98

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Analysis of algorithms (68W40)

Recommendations

• Efficient parallel algorithms for shortest paths in planar digraphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• scientific article; zbMATH DE number 176745
• Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems
• Efficient parallel algorithms for planar st-graphs

Cites work

• A note on two problems in connexion with graphs
• A simple parallel tree contraction algorithm
• A Theorem on Boolean Matrices
• Designing networks with compact routing tables
• Deterministic coin tossing with applications to optimal parallel list ranking
• Efficient parallel algorithms for shortest paths in planar graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 139775 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• New Bounds on the Complexity of the Shortest Path Problem
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Parallel Matrix and Graph Algorithms
• Planar graph decomposition and all pairs shortest paths

Cited in

(15)

• Parallel algorithms for shortest path problems in polygons
• Efficient parallel algorithms for shortest paths in planar digraphs
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• Efficient parallel algorithms for planar st-graphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• scientific article; zbMATH DE number 56471 (Why is no real title available?)
• scientific article; zbMATH DE number 176745 (Why is no real title available?)
• Planar graph decomposition and all pairs shortest paths
• Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems
• Efficient parallel algorithms for shortest paths in planar graphs
• Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems
• scientific article; zbMATH DE number 2208627 (Why is no real title available?)
• Faster shortest-path algorithms for planar graphs
• A simple parallel algorithm for the single-source shortest path problem on planar digraphs

Describes a project that uses

Uses Software

• Algorithm 97

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056111)