All-pairs almost shortest paths

被引:158
|
作者
Dor, D [1 ]
Halperin, S [1 ]
Zwick, U [1 ]
机构
[1] Tel Aviv Univ, Dept Comp Sci, IL-69978 Tel Aviv, Israel
关键词
graph algorithms; shortest paths; approximation algorithms; spanners; emulators;
D O I
10.1137/S0097539797327908
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Let G = (V, E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth et al. [SIAM J. Comput., 28 (1999), pp. 1167 1181], we describe an (O) over tilde(min{n(3/2)m(1/2),n(7/3)})-time algorithm APASP(2) for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP(2) is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k > 2, we describe an (O) over tilde(min{n(2-2/(k+2))m(2/(k+2)),n(2+2/(3k-2))})-time algorithm APASP(k) for computing all distances in G with an additive one-sided error of at most k. We also give an (O) over tilde(n(2))-time algorithm APASP(infinity) for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in (O) over tilde(n(2)) time. We say that a weighted graph F = (V, E') k-emulates an unweighted graph G = (V, E) if for every u, v is an element of V we have delta(G)(u, v) less than or equal to delta(F)(u, v) less than or equal to delta(G)(u, v) + k. We show that every unweighted graph on n vertices has a 2-emulator with (O) over tilde(n(3/2)) edges and a 4-emulator with (O) over tilde(n(4/3)) edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with (O) over tilde(n(3/2)) edges and that such a 3-spanner can be built in (O) over tilde(mn(1/2)) time. We also describe an (O) over tilde(n(m(2/3)+n))-time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.
引用
收藏
页码:1740 / 1759
页数:20
相关论文
共 50 条
  • [21] A branch-checking algorithm for all-pairs shortest paths
    Duin, C
    ALGORITHMICA, 2005, 41 (02) : 131 - 145
  • [22] From Circuit Complexity to Faster All-Pairs Shortest Paths
    Williams, R. Ryan
    SIAM REVIEW, 2021, 63 (03) : 559 - 582
  • [23] More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
    Chan, Timothy M.
    STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 590 - 598
  • [24] Faster All-Pairs Shortest Paths Via Circuit Complexity
    Williams, Ryan
    STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 664 - 673
  • [25] Dynamic approximate all-pairs shortest paths in undirected graphs
    Roditty, L
    Zwick, U
    45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, : 499 - 508
  • [26] MORE ALGORITHMS FOR ALL-PAIRS SHORTEST PATHS IN WEIGHTED GRAPHS
    Chan, Timothy M.
    SIAM JOURNAL ON COMPUTING, 2010, 39 (05) : 2075 - 2089
  • [27] Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths
    Kratsch, Stefan
    Nelles, Florian
    37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
  • [28] FASTER ALL-PAIRS SHORTEST PATHS VIA CIRCUIT COMPLEXITY
    Williams, R. Ryan
    SIAM JOURNAL ON COMPUTING, 2018, 47 (05) : 1965 - 1985
  • [29] Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
    Planken, Leon
    de Weerdt, Mathijs
    van der Krogt, Roman
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2012, 43 : 353 - 388
  • [30] All-pairs shortest paths algorithm for highdimensional sparse graphs
    Urakov, A. R.
    Timeryaev, T., V
    PRIKLADNAYA DISKRETNAYA MATEMATIKA, 2013, 19 (01): : 84 - 92