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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number2344424
JournalACM Transactions on Algorithms
Volume8
Issue number4
DOIs
StatePublished - Sep 2012
Externally publishedYes

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'All-Pairs shortest paths for unweighted undirected graphs in o(mn) time'. Together they form a unique fingerprint.

Cite this