Abstract
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) |
---|---|
Article number | 2344424 |
Journal | ACM Transactions on Algorithms |
Volume | 8 |
Issue number | 4 |
DOIs | |
State | Published - Sep 2012 |
Externally published | Yes |
ASJC Scopus subject areas
- Mathematics (miscellaneous)