Shortest path queries in digraphs of small treewidth
From MaRDI portal
Publication:4645182
DOI10.1007/3-540-60084-1_78zbMATH Open1412.68164OpenAlexW1602042964MaRDI QIDQ4645182FDOQ4645182
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)
Cites Work
- Network flows. Theory, algorithms, and applications.
- Fibonacci heaps and their uses in improved network optimization algorithms
- Title not available (Why is that?)
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph minors. II. Algorithmic aspects of tree-width
- A linear time algorithm for finding tree-decompositions of small treewidth
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Computing on a free tree via complexity-preserving mappings
- Faster shortest-path algorithms for planar graphs
- Dynamic algorithms for shortest paths in planar graphs
- Planar graph decomposition and all pairs shortest paths
- Title not available (Why is that?)
- On-line and dynamic algorithms for shortest path problems
- Searching among intervals and compact routing tables
Cited In (14)
- Semi-dynamic breadth-first search in digraphs
- Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
- 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
- Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
- Compact navigation and distance oracles for graphs with small treewidth
- Semi-dynamic shortest paths and breadth-first search in digraphs
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Optimal parallel shortest paths in small treewidth digraphs
- Shortest beer path queries in outerplanar graphs
- Compact navigation and distance oracles for graphs with small treewidth
- Dynamic algorithms for graphs of bounded treewidth
- Efficient algorithms for shortest path queries in planar digraphs
- Shortest path algorithms for nearly acyclic directed 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)
