All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time

被引：28

作者：

Chan, Timothy M. ^{[1
]}

机构：

[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2012年 / 8卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Algorithms; Theory; Graph algorithms; shortest paths; word RAM; ALGORITHM;

D O I：

10.1145/2344422.2344424

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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(n2log2logn/logn) 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.

引用

页数：17

共 34 条

[1] FASTER ALGORITHMS FOR THE SHORTEST-PATH PROBLEM [J].

AHUJA, RK ;

MEHLHORN, K ;

ORLIN, JB ;

TARJAN, RE .

JOURNAL OF THE ACM, 1990, 37 (02) :213-223

[2] Fast estimation of diameter and shortest paths (without matrix multiplication) [J].

Aingworth, D ;

Chekuri, C ;

Indyk, P ;

Motwani, R .

SIAM JOURNAL ON COMPUTING, 1999, 28 (04) :1167-1181

[3] Improved parallel integer sorting without concurrent writing [J].

Albers, S ;

Hagerup, T .

INFORMATION AND COMPUTATION, 1997, 136 (01) :25-51

[4] On the exponent of the all pairs shortest path problem [J].

Alon, N ;

Galil, Z ;

Margalit, O .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (02) :255-262

[5]

[Anonymous], 1970, Soviet Mathematics Doklady

[6] Regularity Lemmas and Combinatorial Algorithms [J].

Bansal, Nikhil ;

Williams, Ryan .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :745-754

[7]

Buchsbaum A. L., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P279, DOI 10.1145/276698.276764

[8] MORE ALGORITHMS FOR ALL-PAIRS SHORTEST PATHS IN WEIGHTED GRAPHS [J].

Chan, Timothy M. .

SIAM JOURNAL ON COMPUTING, 2010, 39 (05) :2075-2089

[9] MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS [J].

COPPERSMITH, D ;

WINOGRAD, S .

JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) :251-280

[10] A MORE EFFICIENT ALGORITHM FOR THE MIN-PLUS MULTIPLICATION [J].

DOBOSIEWICZ, W .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1990, 32 (1-2) :49-60

← 1 2 3 4 →