Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition

DOI10.1006/JAGM.1996.0048MaRDI QIDQ4895808zbMATH OpenOpenAlexFDO

Authors Edith Cohen

Publication date 3 March 1997

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1996.0048

zbMATH Keywords

reachability problemshortest-paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Efficient parallel algorithms for shortest paths in planar digraphs
• scientific article; zbMATH DE number 176745

Cited in

(12)

• Parallel nested dissection for path algebra computations
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Nearly work-efficient parallel algorithm for digraph reachability
• Nearly work-efficient parallel algorithm for digraph reachability
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Computational Science - ICCS 2004
• Faster shortest-path algorithms for planar graphs
• 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
• Planar separators and parallel polygon triangulation.

This page was built for publication: Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition

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