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> nlog nlog log log n O(mnlog log n/ log n) ifm> nlog log n O(n2 log2 log n/ log n) ifm≤ nlog log n. These represent the best time bounds known for the problem for all m≪ n1.376.We also obtain a similar type of result for the diameter problem for unweighted directed graphs.
|Original language||English (US)|
|Journal||ACM Transactions on Algorithms|
|State||Published - Sep 2012|
ASJC Scopus subject areas
- Mathematics (miscellaneous)