An efficient parallel algorithm for shortest paths in planar layered digraphs

DOI10.1007/BF01294130MaRDI QIDQ1899220zbMATH OpenOpenAlexFDO

Authors Roberto Tamassia, Jeffrey Scott Vitter, Sairam Subramanian

Publication date 18 March 1996

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01294130

zbMATH Keywords

directed graphplanar layered digraphsshortest paths

Mathematics Subject Classification ID

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

Recommendations

• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Efficient parallel algorithms for shortest paths in planar digraphs
• Efficient parallel algorithms for shortest paths in planar graphs
• A simple parallel algorithm for the single-source shortest path problem on planar digraphs
• Optimal parallel algorithms for path problems on planar graphs
• scientific article; zbMATH DE number 56471
• Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
• Efficient parallel algorithms for planar st-graphs
• Efficient parallel algorithms for computing all pair shortest paths in directed graphs

Cites work

• A note on two problems in connexion with graphs
• Applications of a Planar Separator Theorem
• Dynamic maintenance of planar digraphs, with applications
• Efficient Parallel Algorithms for String Editing and Related Problems
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Fast and efficient solution of path algebra problems
• Finding small simple cycle separators for 2-connected planar graphs
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 4049078 (Why is no real title available?)
• scientific article; zbMATH DE number 4064467 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• On a routing problem
• Parallel Transitive Closure and Point Location in Planar Structures
• The parallel computation of minimum cost paths in graphs by stream contraction
• The Recognition of Series Parallel Digraphs

Cited in

(7)

• Efficient parallel algorithms for planar st-graphs
• Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
• Efficient parallel algorithms for shortest paths in planar graphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• scientific article; zbMATH DE number 2208627 (Why is no real title available?)
• A simple parallel algorithm for the single-source shortest path problem on planar digraphs
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances

This page was built for publication: An efficient parallel algorithm for shortest paths in planar layered digraphs

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