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

Timothy M. Chan

doi:10.1145/1109557.1109614

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

Research output: Contribution to conference › Paper › peer-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 > n log² n O(mn log log n/ log n) if m > n log log n O(n² log² 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.

Original language	English (US)
Pages	514-523
Number of pages	10
DOIs	https://doi.org/10.1145/1109557.1109614
State	Published - 2006
Externally published	Yes
Event	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006

Other

Other	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Miami, FL
Period	1/22/06 → 1/24/06

ASJC Scopus subject areas

Software
General Mathematics

Online availability

10.1145/1109557.1109614

Library availability

Discover UIUC Full Text

Cite this

@conference{0eaf896fce714795a45887c769ef1780,

title = "All-pairs shortest paths for unweighted undirected graphs in o(mn) time",

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 > n log2 n O(mn log log n/ log n) if m > n log log n O(n2 log2 log n/ log n) if m ≤ n log 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.",

author = "Chan, {Timothy M.}",

year = "2006",

doi = "10.1145/1109557.1109614",

language = "English (US)",

pages = "514--523",

}

TY - CONF

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

AU - Chan, Timothy M.

PY - 2006

Y1 - 2006

N2 - 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 log2 n O(mn log log n/ log n) if m > n log log n O(n2 log2 log n/ log n) if m ≤ n log 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.

AB - 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 log2 n O(mn log log n/ log n) if m > n log log n O(n2 log2 log n/ log n) if m ≤ n log 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.

UR - http://www.scopus.com/inward/record.url?scp=33244486056&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33244486056&partnerID=8YFLogxK

U2 - 10.1145/1109557.1109614

DO - 10.1145/1109557.1109614

M3 - Paper

AN - SCOPUS:33244486056

SP - 514

EP - 523

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -

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

Abstract

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this