Shortest paths in digraphs of small treewidth. I: Sequential algorithms

DOI10.1007/S004530010016MaRDI QIDQ1578402zbMATH OpenOpenAlexFDO

Authors Shiva Chaudhuri, Christos Zaroliagis

Publication date 17 May 2001

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004530010016

zbMATH Keywords

treewidthshortest pathpartial \(k\)-trees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Shortest path queries in digraphs of small treewidth
• Optimal parallel shortest paths in small treewidth digraphs
• scientific article; zbMATH DE number 1323192
• scientific article; zbMATH DE number 1031380
• Approximating Pathwidth for Graphs of Small Treewidth
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• scientific article; zbMATH DE number 1186513
• Shortest paths in almost acyclic graphs
• Semi-dynamic shortest paths and breadth-first search in digraphs

Cited in

(23)

• Localized and compact data-structure for comparability graphs
• Customizable contraction hierarchies
• A \(c^k n\) 5-approximation algorithm for treewidth
• Shortest path algorithms for nearly acyclic directed graphs
• Shortest path queries in digraphs of small treewidth
• Exact distance oracles for planar graphs
• Search-space size in contraction hierarchies
• The inverse Voronoi problem in graphs. II: Trees
• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
• Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs
• On the power of tree-depth for fully polynomial FPT algorithms
• Distance Labeling for Permutation Graphs
• Efficient algorithms for center problems in cactus networks
• Faster algorithms for quantitative verification in bounded treewidth graphs
• Optimal parallel shortest paths in small treewidth digraphs
• Query efficient implementation of graphs of bounded clique-width
• Bundling all shortest paths
• Simple parallel algorithms for dynamic range products
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Algorithms for algebraic path properties in concurrent systems of constant treewidth components
• Fixed-parameter tractability of treewidth and pathwidth

This page was built for publication: Shortest paths in digraphs of small treewidth. I: Sequential algorithms

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