Shortest path queries in digraphs of small treewidth

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

zbMATH Keywords

tree decompositiondynamic algorithmnegative cycleshort pathshort path tree

Mathematics Subject Classification ID

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