All-pairs shortest paths for unweighted undirected graphs in o(mn) time
From MaRDI portal
Publication:3581545
DOI10.1145/1109557.1109614zbMath1192.05154OpenAlexW4246466944MaRDI QIDQ3581545
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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ 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 ⋮ Compact Navigation and Distance Oracles for Graphs with Small Treewidth ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Efficient algorithms for clique problems ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
This page was built for publication: All-pairs shortest paths for unweighted undirected graphs in o(mn) time
