All-pairs shortest paths for unweighted undirected graphs in o(mn) time

DOI10.1145/1109557.1109614MaRDI QIDQ3581545zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1109557.1109614

Mathematics Subject Classification ID

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

Cited in

(11)

• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• A survey of the all-pairs shortest paths problem and its variants in graphs
• Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings
• Compact navigation and distance oracles for graphs with small treewidth
• Sharing information for the all pairs shortest path problem
• Some results on approximate 1-median selection in metric spaces
• A note on planar graphs with large width parameters and small grid-minors
• Compact navigation and distance oracles for graphs with small treewidth
• Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Efficient algorithms for clique problems

This page was built for publication: All-pairs shortest paths for unweighted undirected graphs in o(mn) time

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