All-pairs shortest paths for unweighted undirected graphs in o(mn) time
From MaRDI portal
Publication:3581545
DOI10.1145/1109557.1109614zbMath1192.05154MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings, 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, Efficient algorithms for clique problems, 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, Compact Navigation and Distance Oracles for Graphs with Small Treewidth
