pith. sign in

arxiv: 2606.26554 · v1 · pith:UBYIR5R4new · submitted 2026-06-25 · 💻 cs.DS

Almost Optimal Multiple Source Shortest Paths and Reachability

Barna Saha , Yinzhan Xu , Christopher Ye This is my paper

Pith reviewed 2026-06-26 02:49 UTC · model grok-4.3

classification 💻 cs.DS
keywords multiple-source shortest pathsreachabilitygraph decompositionBoolean matrix multiplicationundirected graphsdirected graphsshortcut setsdiameter reduction
0
0 comments X

The pith

A novel graph decomposition solves multiple-source shortest paths and reachability in time matching rectangular Boolean matrix multiplication.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an algorithm for multiple-source shortest paths from n^sigma sources in undirected unweighted graphs that runs in time O(n to the power of omega(sigma,1,1)). This time bound interpolates between single-source shortest paths when sigma is zero and all-pairs shortest paths when sigma is one. The same bound holds for multiple-source reachability in directed graphs and extends to shortest paths on DAGs. The key step is a new graph decomposition that reduces both problems directly to rectangular Boolean matrix multiplication. As a consequence the authors obtain an O(n to the power 2.084) algorithm for an O(n)-size shortcut set that reduces graph diameter to O(n to the power 1/3).

Core claim

The authors establish that multiple-source shortest paths on undirected unweighted graphs and multiple-source reachability on directed graphs can both be solved in time matching the time for rectangular Boolean matrix multiplication between an n^sigma by n matrix and an n by n matrix, using a novel graph decomposition technique.

What carries the argument

A novel graph decomposition that reduces the multiple-source shortest-path and reachability problems to rectangular Boolean matrix multiplication without hidden logarithmic or polynomial overhead.

If this is right

  • The running time smoothly interpolates between O(n^2) for single-source shortest paths and O(n^omega) for all-pairs shortest paths.
  • The reachability algorithm is optimal because it matches the known lower bound from rectangular Boolean matrix multiplication.
  • The same decomposition yields an O(n^2.084)-time algorithm for an O(n)-size shortcut set that reduces diameter to O(n^1/3).
  • The reachability result extends to multiple-source shortest paths on directed acyclic graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the decomposition can be adapted to weighted graphs, similar speedups may apply to weighted multiple-source problems.
  • The technique may improve other primitives whose complexity is governed by rectangular matrix multiplication, such as certain forms of transitive closure.
  • Faster multi-source distances could accelerate downstream tasks such as network centrality computations from multiple seeds.

Load-bearing premise

The novel graph decomposition can be computed in the stated time bound and correctly reduces the multiple-source shortest-path and reachability problems to rectangular Boolean matrix multiplication without hidden logarithmic or polynomial overhead.

What would settle it

A family of graphs on which either the decomposition requires more than the claimed time or the reduction to rectangular matrix multiplication incurs an extra polynomial factor in the running time.

Figures

Figures reproduced from arXiv: 2606.26554 by Barna Saha, Christopher Ye, Yinzhan Xu.

Figure 1
Figure 1. Figure 1: Comparison of running times of algorithms for Multiple-Source Reachability on dense graphs when b [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of running times of algorithms for computing shortcut sets in dense graphs with [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Process of growing one cluster until it stops expanding. Here, [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of known algorithms for computing MSSP on unweighted DAGs against known al [PITH_FULL_IMAGE:figures/full_fig_p041_4.png] view at source ↗
read the original abstract

Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\hat{O}(n^\omega) = O(n^{2.372})$ time [Seidel '95] providing significant savings over running $n$ SSSP instances separately. However, if one needs to compute multiple-source shortest paths (MSSP) from a set of $n^\sigma$ vertices, the previously best known running time was $\hat{O}(\min\{n^\omega, n^{2 + \sigma}\})$: either compute APSP or run SSSP from each source. On the other hand, MSSP is only as hard as computing Boolean matrix product (BMM) between an $n^\sigma \times n$ matrix and $n \times n$ matrix, leaving a significant gap. Our first main result is an almost optimal algorithm for MSSP on undirected unweighted graphs running in $\hat{O}(n^{\omega(\sigma, 1, 1)})$ time, which gives a smooth interpolation between the SSSP and APSP algorithms. The main technical tool behind our result is a novel graph decomposition, which may be of independent interest. Next, we study the multiple-source reachability problem, where we need to determine whether a given set of $n^\sigma$ vertices can reach each of the vertices in a given directed graph. Multiple-source reachability can also be solved in $\hat{O}(\min\{n^\omega, n^{2 + \sigma}\})$ time, with the same lower bound from rectangular BMM. We give an optimal algorithm that runs in $\hat{O}(n^{\omega(\sigma, 1, 1)})$ time, again matching the running time for BMM. Our algorithm for multiple-source reachability can be generalized to MSSP on DAGs. As an application, we provide an $O(n^{2.084})$ time algorithm for computing an $\widetilde{O}(n)$-size shortcut set that reduces diameter to $O(n^{1/3})$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims an almost-optimal Õ(n^{ω(σ,1,1)}) algorithm for multiple-source shortest paths (MSSP) from n^σ sources in undirected unweighted graphs, and an optimal algorithm for multiple-source reachability in directed graphs (also generalizing to MSSP on DAGs), both matching rectangular Boolean matrix multiplication time. The key tool is a novel graph decomposition claimed to be computable in the target time with no hidden overhead; an application yields an O(n^{2.084})-time Õ(n)-size shortcut set reducing diameter to O(n^{1/3}).

Significance. If the decomposition is correct, the result closes the gap between the prior Õ(min{n^ω, n^{2+σ}}) bound and the BMM lower bound, giving the first smooth interpolation between SSSP and APSP for MSSP as σ varies. The decomposition itself may be of independent interest.

major comments (1)
  1. [Abstract / main technical tool description] The novel graph decomposition is load-bearing for both main theorems, yet the provided abstract states its existence and time bound without a proof sketch, recurrence, or construction; the full manuscript must supply a complete analysis showing the decomposition is computed in Õ(n^{ω(σ,1,1)}) time and reduces the problems to a single rectangular BMM instance with no extra logarithmic or polynomial factors.
minor comments (2)
  1. [Abstract] Define or cite the rectangular exponent ω(σ,1,1) explicitly when first used.
  2. [Abstract] Clarify whether the Õ notation hides factors depending on σ.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and for noting the potential significance of the results. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract / main technical tool description] The novel graph decomposition is load-bearing for both main theorems, yet the provided abstract states its existence and time bound without a proof sketch, recurrence, or construction; the full manuscript must supply a complete analysis showing the decomposition is computed in Õ(n^{ω(σ,1,1)}) time and reduces the problems to a single rectangular BMM instance with no extra logarithmic or polynomial factors.

    Authors: Abstracts are necessarily concise and omit technical details such as recurrences or proof sketches. The full manuscript supplies the requested complete analysis: Section 3 gives the explicit recursive construction of the decomposition together with the recurrence for its running time, and proves that the decomposition is computed in Õ(n^{ω(σ,1,1)}) time while reducing both MSSP and multiple-source reachability to a single rectangular BMM instance with no additional logarithmic or polynomial factors. The same analysis appears in the reachability section and the DAG-MSSP generalization. revision: no

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The abstract and described claims present a novel graph decomposition as an independent technical tool that reduces MSSP/reachability to a single rectangular BMM instance while matching the ω(σ,1,1) exponent. No equations, recurrences, or self-citations are exhibited that reduce the claimed running time or correctness to a fitted parameter, prior self-result, or input by construction. The result is positioned as closing a gap between prior min{n^ω, n^{2+σ}} bounds and the BMM lower bound via new machinery, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the known rectangular matrix-multiplication exponent and the correctness of an unpublished graph decomposition; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Fast algorithms exist for rectangular Boolean matrix multiplication with exponent ω(σ,1,1)
    The running time is expressed directly in terms of this known quantity.

pith-pipeline@v0.9.1-grok · 5963 in / 1300 out tokens · 58220 ms · 2026-06-26T02:49:25.766287+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

84 extracted references · 1 linked inside Pith

  1. [1]

    The 4/3 additive spanner exponent is tight

    Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. Journal of the ACM (JACM) , 64(4):1--20, 2017

    2017

  2. [2]

    Stronger 3-sum lower bounds for approximate distance oracles via additive combinatorics

    Amir Abboud, Karl Bringmann, and Nick Fischer. Stronger 3-sum lower bounds for approximate distance oracles via additive combinatorics. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 391--404, 2023

    2023

  3. [3]

    Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond

    Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1487--1500, 2022

    2022

  4. [4]

    Fast estimation of diameter and shortest paths (without matrix multiplication)

    Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing , 28(4):1167--1181, 1999

    1999

  5. [5]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams , Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2005--2039. SIAM, 2025

    2005

  6. [6]

    On the exponent of the all pairs shortest path problem

    Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences , 54(2):255--262, 1997

    1997

  7. [7]

    Near-optimal decremental SSSP in dense weighted digraphs

    Aaron Bernstein, Maximilian Probst Gutenberg, and Christian Wulff - Nilsen. Near-optimal decremental SSSP in dense weighted digraphs. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 1112--1122, 2020

    2020

  8. [8]

    Folklore sampling is optimal for exact hopsets: Confirming the n barrier

    Greg Bodwin and Gary Hoppenworth. Folklore sampling is optimal for exact hopsets: Confirming the n barrier. In IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 701--720. IEEE, 2023

    2023

  9. [9]

    Faster algorithms for approximate distance oracles and all-pairs small stretch paths

    Surender Baswana and Telikepalli Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages 591--602. IEEE, 2006

    2006

  10. [10]

    New constructions of (alpha, beta)-spanners and purely additive spanners

    Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In SODA , volume 5, pages 672--681, 2005

    2005

  11. [11]

    Negative-weight single-source shortest paths in near-linear time

    Aaron Bernstein, Danupon Nanongkai, and Christian Wulff - Nilsen. Negative-weight single-source shortest paths in near-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS , 2022

    2022

  12. [12]

    4 vs 7 sparse undirected unweighted diameter is seth-hard at time n 4/3

    \'E douard Bonnet. 4 vs 7 sparse undirected unweighted diameter is seth-hard at time n 4/3. ACM Transactions on Algorithms (TALG) , 18(2):1--14, 2022

    2022

  13. [13]

    Towards tight approximation bounds for graph diameter and eccentricities

    Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 267--280, 2018

    2018

  14. [14]

    Very sparse additive spanners and emulators

    Gregory Bodwin and Virginia Vassilevska Williams . Very sparse additive spanners and emulators. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science , pages 377--382, 2015

    2015

  15. [15]

    Fast and compact exact distance oracle for planar graphs

    Vincent Cohen-Addad , Søren Dahlgaard, and Christian Wulff-Nilsen . Fast and compact exact distance oracle for planar graphs. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 962--973, 2017

    2017

  16. [16]

    Almost optimal distance oracles for planar graphs

    Panagiotis Charalampopoulos, Pawe Gawrychowski, Shay Mozes, and Oren Weimann. Almost optimal distance oracles for planar graphs. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , page 138–151. Association for Computing Machinery, 2019

    2019

  17. [17]

    New bounds for approximating extremal distances in undirected graphs

    Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal distances in undirected graphs. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages 363--376. SIAM, 2016

    2016

  18. [18]

    Timothy M. Chan. All-pairs shortest paths with real weights in O(n^3 / n) time. In 9th International Workshop on Algorithms and Data Structures, WADS , 2005

    2005

  19. [19]

    Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. , 39(5), 2010

    2010

  20. [20]

    New additive spanners

    Shiri Chechik. New additive spanners. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages 498--512. SIAM, 2013

    2013

  21. [21]

    Approximate distance oracles with constant query time

    Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , page 654–663. Association for Computing Machinery, 2014

    2014

  22. [22]

    New approximation algorithms and reductions for n-pairs shortest paths and all-nodes shortest cycles

    Shiri Chechik, Itay Hoch, and Gur Lifshitz. New approximation algorithms and reductions for n-pairs shortest paths and all-nodes shortest cycles. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 5207--5238. SIAM, 2025

    2025

  23. [23]

    Better approximation algorithms for the graph diameter

    Shiri Chechik, Daniel H Larkin, Liam Roditty, Grant Schoenebeck, Robert E Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1041--1052. SIAM, 2014

    2014

  24. [24]

    Compact routing with minimum stretch

    Lenore J Cowen. Compact routing with minimum stretch. Journal of Algorithms , 38(1):170--183, 2001

    2001

  25. [25]

    Chan, Virginia Vassilevska Williams , and Yinzhan Xu

    Timothy M. Chan, Virginia Vassilevska Williams , and Yinzhan Xu. Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 47:1--47:21, 2021

    2021

  26. [26]

    Compact roundtrip routing in directed networks

    Lenore J Cowen and Christopher G Wagner. Compact roundtrip routing in directed networks. In Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing , pages 51--59, 2000

    2000

  27. [27]

    Nearly 2-approximate distance oracles in subquadratic time

    Shiri Chechik and Tianyi Zhang. Nearly 2-approximate distance oracles in subquadratic time. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 551--580. SIAM, 2022

    2022

  28. [28]

    Fast 2-approximate all-pairs shortest paths

    Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams , and Tijn de Vos. Fast 2-approximate all-pairs shortest paths. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 , pages 4728--4757, 2024

    2024

  29. [29]

    All pairs almost shortest paths

    Dorit Dor, Shay Halperin, and Uri Zwick. All pairs almost shortest paths. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS 1996 , pages 452--461, 1996

    1996

  30. [30]

    All-pairs almost shortest paths

    Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing , 29(5):1740--1759, 2000

    2000

  31. [31]

    Dijkstra

    Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math. , 50:269--271, 1959

    1959

  32. [32]

    Approximation algorithms and hardness for n-pairs shortest paths and all-nodes shortest cycles

    Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams , and Nicole Wein. Approximation algorithms and hardness for n-pairs shortest paths and all-nodes shortest cycles. In IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 290--300. IEEE, 2022

    2022

  33. [33]

    New additive approximations for shortest paths and cycles

    Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams , and Ziqian Zhong. New additive approximations for shortest paths and cycles. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 , pages 50:1--50:10, 2022

    2022

  34. [34]

    Hardness of approximate diameter: Now for undirected graphs

    Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams . Hardness of approximate diameter: Now for undirected graphs. Journal of the ACM , 72(1):1--32, 2025

    2025

  35. [35]

    A more efficient algorithm for the min-plus multiplication

    Wlodzimierz Dobosiewicz. A more efficient algorithm for the min-plus multiplication. Int. J. Computer Math. , 32, 1990

    1990

  36. [36]

    Improved weighted additive spanners

    Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved weighted additive spanners. Distributed Computing , 36(3):385--394, 2023

    2023

  37. [37]

    Faster multi-source directed reachability via shortcuts and matrix multiplication

    Michael Elkin and Chhaya Trehan. Faster multi-source directed reachability via shortcuts and matrix multiplication. arXiv preprint arXiv:2401.05628 , 2024

    arXiv 2024

  38. [38]

    Faster multi-source reachability and approximate distances via shortcuts, hopsets and matrix multiplication

    Michael Elkin and Chhaya Trehan. Faster multi-source reachability and approximate distances via shortcuts, hopsets and matrix multiplication. arXiv preprint arXiv:2507.13470 , 2025

    Pith/arXiv arXiv 2025

  39. [39]

    Jeremy T. Fineman. Nearly work-efficient parallel algorithm for digraph reachability. SIAM J. Comput. , 49(5), 2020

    2020

  40. [40]

    Boolean matrix multiplication and transitive closure

    Michael J Fischer and Albert R Meyer. Boolean matrix multiplication and transitive closure. In 12th annual symposium on switching and automata theory (swat 1971) , pages 129--131. IEEE, 1971

    1971

  41. [41]

    A faster distributed single-source shortest paths algorithm

    Sebastian Forster and Danupon Nanongkai. A faster distributed single-source shortest paths algorithm. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 686--697, 2018

    2018

  42. [42]

    Spanners and message distribution in networks

    Arthur M Farley, Andrzej Proskurowski, Daniel Zappala, and Kurt Windisch. Spanners and message distribution in networks. Discrete Applied Mathematics , 137(2):159--171, 2004

    2004

  43. [43]

    Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput. , 5(1):83--89, 1976

    1976

  44. [44]

    Fredman and Robert Endre Tarjan

    Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM , 34(3):596--615, 1987

    1987

  45. [45]

    Faster replacement paths and distance sensitivity oracles

    Fabrizio Grandoni and Virginia Vassilevska Williams . Faster replacement paths and distance sensitivity oracles. ACM Transactions on Algorithms (TALG) , 16(1):1--25, 2019

    2019

  46. [46]

    Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary

    Maximilian Probst Gutenberg and Christian Wulff - Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In 31st ACM-SIAM Symposium on Discrete Algorithms, SODA , 2020

    2020

  47. [47]

    Improved algorithm for all pairs shortest paths

    Yijie Han. Improved algorithm for all pairs shortest paths. Inf. Process. Lett. , 91(5), 2004

    2004

  48. [48]

    Achieving O(n^3/ n) time for all pairs shortest paths by using a smaller table

    Yijie Han. Achieving O(n^3/ n) time for all pairs shortest paths by using a smaller table. In 21st International Conference on Computers and Their Applications, CATA , 2006

    2006

  49. [49]

    Improved roundtrip spanners, emulators, and directed girth approximation

    Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams , and Zixuan Xu. Improved roundtrip spanners, emulators, and directed girth approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4641--4669. SIAM, 2024

    2024

  50. [50]

    Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

    Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In 46th Annual Symposium on the Theory of Computing, STOC , 2014

    2014

  51. [51]

    Improved algorithms for decremental single-source reachability on directed graphs

    Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP) , pages 725--736, 2015

    2015

  52. [52]

    Simple linear-size additive emulators

    Gary Hoppenworth. Simple linear-size additive emulators. In 2024 Symposium on Simplicity in Algorithms (SOSA) , pages 1--8. SIAM, 2024

    2024

  53. [53]

    Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts

    Shang-En Huang and Seth Pettie. Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts. SIAM Journal on Discrete Mathematics , 35(3):2129--2144, 2021

    2021

  54. [54]

    An O(n^3 n/ ^2 n) time algorithm for all pairs shortest paths

    Yijie Han and Tadao Takaoka. An O(n^3 n/ ^2 n) time algorithm for all pairs shortest paths. In 13th Scandinavian Workshop on Algorithm Theory, SWAT , 2012

    2012

  55. [55]

    Improved additive approximation algorithms for APSP

    Ce Jin, Yael Kirkpatrick, Michal Stawarz, and Virginia Vassilevska Williams . Improved additive approximation algorithms for APSP . In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3639--3651, 2026

    2026

  56. [56]

    Removing additive structure in 3sum-based reductions

    Ce Jin and Yinzhan Xu. Removing additive structure in 3sum-based reductions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 405--418, 2023

    2023

  57. [57]

    Beating matrix multiplication for n^ 1/3 -directed shortcuts

    Shimon Kogan and Merav Parter. Beating matrix multiplication for n^ 1/3 -directed shortcuts. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , pages 82--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2022

    2022

  58. [58]

    New diameter-reducing shortcuts and directed hopsets: Breaking the barrier

    Shimon Kogan and Merav Parter. New diameter-reducing shortcuts and directed hopsets: Breaking the barrier. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1326--1341. SIAM, 2022

    2022

  59. [59]

    Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers

    Shimon Kogan and Merav Parter. Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 212--239, 2023

    2023

  60. [60]

    New additive emulators

    Shimon Kogan and Merav Parter. New additive emulators. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages 85--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  61. [61]

    Klein and Sairam Subramanian

    Philip N. Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. J. Algorithms , 25(2):205--220, 1997

    1997

  62. [62]

    Liu, Arun Jambulapati, and Aaron Sidford

    Yang P. Liu, Arun Jambulapati, and Aaron Sidford. Parallel reachability in almost linear work and square root depth. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 1664--1686, 2019

    2019

  63. [63]

    Efficient determination of the transitive closure of a directed graph

    Ian Munro. Efficient determination of the transitive closure of a directed graph. Information Processing Letters , 1(2):56--58, 1971

    1971

  64. [64]

    A new approach to all-pairs shortest paths on real-weighted graphs

    Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science , 312(1):47--74, 2004

    2004

  65. [65]

    Distance oracles beyond the thorup-zwick bound

    Mihai Patrascu and Liam Roditty. Distance oracles beyond the thorup-zwick bound. In IEEE 51st Annual Symposium on Foundations of Computer Science , pages 815--823. IEEE, 2010

    2010

  66. [66]

    Graph spanners

    David Peleg and Alejandro A Sch \"a ffer. Graph spanners. Journal of graph theory , 13(1):99--116, 1989

    1989

  67. [67]

    A trade-off between space and efficiency for routing tables

    David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM (JACM) , 36(3):510--530, 1989

    1989

  68. [68]

    Roundtrip spanners and roundtrip routing in directed graphs

    Liam Roditty, Mikkel Thorup, and Uri Zwick. Roundtrip spanners and roundtrip routing in directed graphs. ACM Transactions on Algorithms (TALG) , 4(3):1--17, 2008

    2008

  69. [69]

    Fast approximation algorithms for the diameter and radius of sparse graphs

    Liam Roditty and Virginia Vassilevska Williams . Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing , pages 515--524, 2013

    2013

  70. [70]

    On the all-pairs-shortest-path problem in unweighted undirected graphs

    Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of computer and system sciences , 51(3):400--403, 1995

    1995

  71. [71]

    Faster approximate all pairs shortest paths

    Barna Saha and Christopher Ye. Faster approximate all pairs shortest paths. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 , pages 4758--4827, 2024

    2024

  72. [72]

    Shoshan and U

    A. Shoshan and U. Zwick. All pairs shortest paths in undirected graphs with integer weights. In 40th Annual Symposium on Foundations of Computer Science , pages 605--614, 1999

    1999

  73. [73]

    A new upper bound on the complexity of the all pairs shortest path problem

    Tadao Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Inf. Process. Lett. , 43(4), 1992

    1992

  74. [74]

    Subcubic cost algorithms for the all pairs shortest path problem

    Tadao Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica , 20(3), 1998

    1998

  75. [75]

    Compact oracles for reachability and approximate distances in planar digraphs

    Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM , 51(6):993–1024, 2004

    2004

  76. [76]

    Compact routing schemes

    Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures , pages 1--10, 2001

    2001

  77. [77]

    Approximate distance oracles

    Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM) , 52(1):1--24, 2005

    2005

  78. [78]

    Spanners and emulators with sublinear distance errors

    Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , pages 802--809, 2006

    2006

  79. [79]

    Ullman and Mihalis Yannakakis

    Jeffrey D. Ullman and Mihalis Yannakakis. High-probability parallel transitive-closure algorithms. SIAM J. Comput. , 20(1):100--125, 1991

    1991

  80. [80]

    Simpler and higher lower bounds for shortcut sets

    Virginia Vassilevska Williams , Yinzhan Xu, and Zixuan Xu. Simpler and higher lower bounds for shortcut sets. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2643--2656. SIAM, 2024

    2024

Showing first 80 references.