Optimal parallel shortest paths in small treewidth digraphs

DOI10.1007/3-540-60313-1_132MaRDI QIDQ6102289zbMATH OpenOpenAlexFDO

Authors Shiva Chaudhuri, Christos Zaroliagis

Publication date 8 May 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60313-1_132

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) 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

• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Efficient parallel algorithms for shortest paths in planar digraphs
• Shortest path queries in digraphs of small treewidth
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• scientific article; zbMATH DE number 176745

Cites work

• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1555943 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• On-line and dynamic algorithms for shortest path problems
• Parallel algorithms with optimal speedup for bounded treewidth
• Shortest path queries in digraphs of small treewidth

Cited in

(5)

• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs
• Shortest path queries in digraphs of small treewidth

This page was built for publication: Optimal parallel shortest paths in small treewidth digraphs

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