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

DOI10.1016/S0304-3975(98)00021-8MaRDI QIDQ1274331zbMATH OpenOpenAlexFDO

Authors Christos Zaroliagis, Shiva 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

graph theorytreewidthparallel computingshortest pathPRAMdynamic algorithm

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 107951 (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?)
• 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
• Network flows. Theory, algorithms, and applications.
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• 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

(10)

• A c^k n 5-approximation algorithm for treewidth
• Shortest path queries in digraphs of small treewidth
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Parallel Shortcutting of Rooted Trees
• Optimal parallel shortest paths in small treewidth digraphs
• Query efficient implementation of graphs of bounded clique-width
• Simple parallel algorithms for dynamic range products
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Improved processor bounds for parallel algorithms for weighted directed graphs
• Fixed-parameter tractability of treewidth and pathwidth

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

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