All-pairs shortest paths algorithm for high-dimensional sparse graphs

MaRDI QIDQ5150562zbMATH OpenFDO

Authors A. R. Urakov, T. V. Timeryaev

Publication date 15 February 2021

Full work available at URL https://arxiv.org/abs/1308.1568, http://mathnet.ru/eng/pdm403

zbMATH Keywords

sparse graphsgraph assemblyAPSPgraph disassembly

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• scientific article; zbMATH DE number 2086613
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• All-pairs shortest paths in \(O(n^2)\) time with high probability
• Two fast algorithms for all-pairs shortest paths

Cites work

• A note on two problems in connexion with graphs
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Efficient Algorithms for Shortest Paths in Sparse Networks
• On a routing problem
• Using weighted graphs features for fast searching their parameters

Cited in

(1)

• All-Pairs Min-Cut in Sparse Networks

Describes a project that uses

Uses Software

• Algorithm 97
• DIMACS

This page was built for publication: All-pairs shortest paths algorithm for high-dimensional sparse graphs

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