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

被引：27
作者：
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
    AHUJA, RK
    MEHLHORN, K
    ORLIN, JB
    TARJAN, RE
    [J]. JOURNAL OF THE ACM, 1990, 37 (02) : 213 - 223
  • [2] Fast estimation of diameter and shortest paths (without matrix multiplication)
    Aingworth, D
    Chekuri, C
    Indyk, P
    Motwani, R
    [J]. SIAM JOURNAL ON COMPUTING, 1999, 28 (04) : 1167 - 1181
  • [3] Improved parallel integer sorting without concurrent writing
    Albers, S
    Hagerup, T
    [J]. INFORMATION AND COMPUTATION, 1997, 136 (01) : 25 - 51
  • [4] On the exponent of the all pairs shortest path problem
    Alon, N
    Galil, Z
    Margalit, O
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (02) : 255 - 262
  • [5] [Anonymous], 1970, Soviet Mathematics Doklady
  • [6] Regularity Lemmas and Combinatorial Algorithms
    Bansal, Nikhil
    Williams, Ryan
    [J]. 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
    Chan, Timothy M.
    [J]. SIAM JOURNAL ON COMPUTING, 2010, 39 (05) : 2075 - 2089
  • [9] MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS
    COPPERSMITH, D
    WINOGRAD, S
    [J]. JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) : 251 - 280
  • [10] A MORE EFFICIENT ALGORITHM FOR THE MIN-PLUS MULTIPLICATION
    DOBOSIEWICZ, W
    [J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1990, 32 (1-2) : 49 - 60
1234