Computing all-pairs shortest paths by leveraging low treewidth
From MaRDI portal
Publication:2887076
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.
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
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
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)
