Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms

DOI10.1016/S0304-3975(98)00021-8zbMath0943.68185OpenAlexW2048362350MaRDI QIDQ1274331

Christos D. Zaroliagis, Shiva P. Chaudhuri

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00021-8

zbMATH Keywords

shortest pathgraph theorytreewidthparallel computingPRAMdynamic algorithm

Mathematics Subject Classification ID

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

Related Items (5)

Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Simple Parallel Algorithms for Dynamic Range Products ⋮ Query efficient implementation of graphs of bounded clique-width ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 Finding Lowest Common Ancestors: Simplification and Parallelization
• 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

This page was built for publication: Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms