Optimal parallel shortest paths in small treewidth digraphs

DOI10.1007/3-540-60313-1_132zbMath1512.68201OpenAlexW1713454487MaRDI QIDQ6102289

Shiva P. Chaudhuri, Christos D. 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

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems

Cites Work

• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. II. Algorithmic aspects of tree-width
• On-line and dynamic algorithms for shortest path problems
• Shortest path queries in digraphs of small treewidth
• Parallel algorithms with optimal speedup for bounded treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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