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

✍ Scribed by Chan, Timothy M.

• Book ID: 125521674
• Publisher: Association for Computing Machinery
• Year: 2012
• Tongue: English
• Weight: 182 KB
• Volume: 8
• Category: Article
• ISSN: 1549-6325
• DOI: 10.1145/2344422.2344424

✦ Synopsis

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
m

n
log log
n
O
(
n
^2^
log
^2^
log
n
/log
n
) if
m
≤
n
log log
n
.

These represent the best time bounds known for the problem for all
m
≪
n
^1.376^
. We also obtain a similar type of result for the diameter problem for unweighted directed graphs.