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

partial \(k\)-treesshortest pathtreewidth

Mathematics Subject Classification ID

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

Review text

An algorithm is developed for answering shortest path queries on graphs with constant treewidth (i.e., partial \(k\)-trees for constant \(k\)), by employing an amount of preprocessing which is linear in the size of the graph. Distance queries can be answered in time proportional to the inverse of the Ackermann function evaluated at the number \(n\) of vertices. A sublinear algorithm is given for updating edge weights dynamically.

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

(26)

• Localized and compact data-structure for comparability graphs
• Shortest path algorithms for nearly acyclic directed graphs
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Query efficient implementation of graphs of bounded clique-width
• Faster algorithms for quantitative verification in bounded treewidth graphs
• Bundling all shortest paths
• Efficient algorithms for center problems in cactus networks
• The inverse Voronoi problem in graphs. II: Trees
• A c^k n 5-approximation algorithm for treewidth
• Algorithms for algebraic path properties in concurrent systems of constant treewidth components
• Fixed-parameter tractability of treewidth and pathwidth
• Search-space size in contraction hierarchies
• On the power of tree-depth for fully polynomial FPT algorithms
• Distance Labeling for Permutation Graphs
• Simple parallel algorithms for dynamic range products
• Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs
• Shortest path queries in digraphs of small treewidth
• Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
• Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
• Customizable contraction hierarchies
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Exact distance oracles for planar graphs
• Optimal parallel shortest paths in small treewidth digraphs
• Shortest beer path queries in digraphs with bounded treewidth
• A WSPD, separator and small tree cover for c-packed graphs
• Algorithms for graphs of bounded treewidth via orthogonal range searching

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)