Computing All-Pairs Shortest Paths by Leveraging Low Treewidth

DOI10.1613/jair.3509zbMath1244.68062arXiv1401.4609OpenAlexW2423358376MaRDI QIDQ2887076

Mathijs de Weerdt, Roman P. J. van der Krogt, Léon R. Planken

Publication date: 16 May 2012

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.4609

zbMATH Keywords

directed graphsefficient algorithmsall-pairs shortest paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Search-space size in contraction hierarchies ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ Dynamic temporal decoupling ⋮ Flexibility and decoupling in simple temporal networks ⋮ Sufficient and necessary conditions for solution finding in valuation-based systems ⋮ Efficient single-pair all-shortest-path query processing for massive dynamic networks ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ Solving strong controllability of temporal problems with uncertainty using SMT ⋮ Customizable Contraction Hierarchies

Uses Software

• SMT-LIB

This page was built for publication: Computing All-Pairs Shortest Paths by Leveraging Low Treewidth