Shortest path queries in digraphs of small treewidth
From MaRDI portal
Publication:4645182
DOI10.1007/3-540-60084-1_78zbMath1412.68164OpenAlexW1602042964MaRDI QIDQ4645182
Shiva P. Chaudhuri, Christos D. 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
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items (6)
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 paths in digraphs of small treewidth. II: Optimal parallel algorithms ⋮ Dynamic algorithms for graphs of bounded treewidth ⋮ Semi-dynamic breadth-first search in digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dynamic algorithms for shortest paths in planar graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Computing on a free tree via complexity-preserving mappings
- Graph minors. II. Algorithmic aspects of tree-width
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Planar graph decomposition and all pairs shortest paths
- On-line and dynamic algorithms for shortest path problems
- Searching among intervals and compact routing tables
- Fibonacci heaps and their uses in improved network optimization algorithms
- A linear time algorithm for finding tree-decompositions of small treewidth
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Shortest path queries in digraphs of small treewidth