๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Chan, Timothy M.

Book ID
125521673
Publisher
Association for Computing Machinery
Year
2012
Tongue
English
Weight
182 KB
Volume
8
Category
Article
ISSN
1549-6325

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

All-pairs shortest paths for unweighted
All-pairs shortest paths for unweighted undirected graphs in o ( mn ) time
โœ Chan, Timothy M. ๐Ÿ“‚ Article ๐Ÿ“… 2012 ๐Ÿ› Association for Computing Machinery ๐ŸŒ English โš– 182 KB

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with __n__ vertices and __m__ edges. We present new algorithms with the following running times: { __O__ ( __mn__ /log __n__ ) if __m__ > __n__ log __n__ log log log __n__ __O__ ( __mn__ log log __n__ /log __n__ ) if

On the All-Pairs-Shortest-Path Problem i
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
โœ R. Seidel ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno