Computing all-pairs shortest paths by leveraging low treewidth

DOI10.1613/JAIR.3509zbMATH Open1244.68062arXiv1401.4609OpenAlexW2423358376MaRDI QIDQ2887076FDOQ2887076

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

Publication date: 16 May 2012

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

Abstract: We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d andlt= w_d is the size of the largest minimal separator induced by the vertex ordering d. We show empirically that on both constructed and realistic benchmarks, in many cases the algorithms outperform Floyd-Warshalls as well as Johnsons algorithm, which represent the current state of the art with a run time of O(n^3) and O(nm + n^2 log n), respectively. Our algorithms can be used for spatial and temporal reasoning, such as for the Simple Temporal Problem, which underlines their relevance to the planning and scheduling community.

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

Recommendations

• scientific article; zbMATH DE number 2086613
• A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
• Algorithms and Computation
• Speeding up shortest path algorithms
• A new approach to dynamic all pairs shortest paths
• A new approach to dynamic all pairs shortest paths
• Solving all-pairs shortest path by single-source computations: theory and practice
• Improved algorithm for all pairs shortest paths
• An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
• A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths

zbMATH Keywords

directed graphsefficient algorithmsall-pairs shortest paths

Mathematics Subject Classification ID

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

Cited In (13)

• Customizable contraction hierarchies
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Dynamic temporal decoupling
• Flexibility and decoupling in simple temporal networks
• Shortest path queries in digraphs of small treewidth
• Search-space size in contraction hierarchies
• On the power of tree-depth for fully polynomial FPT algorithms
• An Experimental Study of the Treewidth of Real-World Graph Data
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• Sufficient and necessary conditions for solution finding in valuation-based systems
• Fission: Practical algorithms for computing minimum balanced node separators
• Solving strong controllability of temporal problems with uncertainty using SMT

Uses Software

• SMT-LIB

This page was built for publication: Computing all-pairs shortest paths by leveraging low treewidth

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