Shortest path queries in digraphs of small treewidth

DOI10.1007/3-540-60084-1_78MaRDI QIDQ4645182zbMATH OpenOpenAlexFDO

Authors Shiva Chaudhuri, Christos Zaroliagis

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_78

zbMATH Keywords

dynamic algorithmnegative cycleshort pathshort path treetree decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Approximating Pathwidth for Graphs of Small Treewidth
• Short path queries in planar graphs in constant time
• Optimal parallel shortest paths in small treewidth digraphs
• Shortest path queries in planar graphs
• scientific article; zbMATH DE number 1031380
• scientific article; zbMATH DE number 1323192
• Computing all-pairs shortest paths by leveraging low treewidth
• Tree-decompositions of small pathwidth

Cites work

• A linear time algorithm for finding tree-decompositions of small treewidth
• Computing on a free tree via complexity-preserving mappings
• Dynamic algorithms for shortest paths in planar graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1555943 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• On-line and dynamic algorithms for shortest path problems
• Planar graph decomposition and all pairs shortest paths
• Searching among intervals and compact routing tables

Cited in

(14)

• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Semi-dynamic breadth-first search in digraphs
• Compact navigation and distance oracles for graphs with small treewidth
• Dynamic algorithms for graphs of bounded treewidth
• Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs
• Compact navigation and distance oracles for graphs with small treewidth
• Semi-dynamic shortest paths and breadth-first search in digraphs
• Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
• Optimal parallel shortest paths in small treewidth digraphs
• Shortest beer path queries in outerplanar graphs
• Efficient algorithms for shortest path queries in planar digraphs
• Shortest path algorithms for nearly acyclic directed graphs
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs

This page was built for publication: Shortest path queries in digraphs of small treewidth

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