betaFeedback

WorksComputer Science

The Cost of Changing Edges for Diameter Computation and More

Abstract

The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in O(1)O(1) time: given an edge ee, return the answer to the problem on either G∖eG \setminus e (decremental) or G∪eG \cup e (incremental). We almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting O(1)O(1)-time queries, thereby improving upon all previous single-failure results [Biló, Cohen, Friedrich, Schirneck, MFCS 2021; Biló, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2023, Algorithmica 2026]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional 1+o(1)1+o(1) factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a 5/35/3 factor in undirected graphs or a 22 factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.

Funding Yael Kirkpatrick: Supported by NSF Grant No. 2141064; Jakob Nogler: Supported by the Akamai Presidential Fellowship and by a fellowship from the Siebel Scholars Foundation; Virginia Vassilevska Williams: Supported by NSF Grant CCF-2330048, BSF Grant 2024233 and a Simons Investigator Award.

Introduction

Dynamic graph algorithms aim to compute and maintain various graph quantities under arbitrarily many changes to the input graph, typically insertions and deletions of vertices or edges. However, in many practical scenarios, changes to the input are naturally confined to small batches and fully dynamic algorithms are often subject to strong lower bounds under standard fine-grained assumptions. This has spurred interest in the sensitivity setting, in which one prepares for a bounded number of changes to the original input data. When the allowed changes are only deletions, the setting is often referred to as “fault tolerant” or “emergency”, as deletions of edges from the input graph can represent failures or faults in the network.

Formally, a data structure with sensitivity for problem PP preprocesses an instance pp of size nn in time P(n)P(n). Upon receiving a batch of at most dd changes to pp, it must output the solution for the modified instance in query time Q(n)Q(n). Crucially, these updates are independent and do not compound; while many distinct queries can be performed on the original instance pp, each update applies only to the initial preprocessed state. Many key problems in graph algorithms have been studied under the sensitivity setting in the past, including connectivity [DP20, DP10, PT07, HN16], reachability [BLM12, BCR15, BCR16, Cho16], single source shortest paths (SSSP) [KB10, Par15, BGLP16a, BGLP16b, GV12, HKIM24, Ber10, CZ24], all-pairs shortest paths (APSP) [KB10, BK09b, BGLP14, CCFK17, GV12, PP18] and graph spanners [BCP12, BGG+15].

This paper focuses on sensitivity algorithms for vertex eccentricities ecc⁡G(v)\operatorname{ecc}_G(v) (the maximum distance from vv to any node uu), the diameter diam⁡(G)\operatorname{diam}(G) (the maximum eccentricity), and the radius radius⁡(G)\operatorname{radius}(G) (the minimum eccentricity). These parameters measure how fast information spreads, informing decisions such as network controller placement. As exact computation is hard under fine-grained assumptions [RV13, AVW16], significant work has focused on approximations in static [ACIM99, BRS+18, CLR+14] and dynamic [AHR+19] settings. Henzinger et al. Henzinger et al. [HLNV17] initiated the sensitivity study with fine-grained lower bounds, followed by several works [BCC+26, BCC+22, BCFS21] focused on upper bounds.

Some Wishful Thinking: Our ideal objective for the sensitivity versions of diameter, eccentricities, and radius (in both exact and approximate settings) is to achieve a preprocessing time PP matching the static problem’s complexity and a query time Q=O(1)Q = O(1). This could be realized through a tight reduction or by developing a new oracle with equivalent preprocessing costs. In the exact setting, since no better algorithm for the problems of interest is currently known than computing APSP, if PP already matches the runtime of computing APSP on the specific graph, this would be similarly significant.

Naturally, achieving the same bounds in the sensitivity setting as in the static version is a very ambitious goal, as the sensitivity setting often introduces additional hardness. For instance, in weighted graphs, decremental diameter is hard under the APSP hypothesis [HLNV17], while its static relationship to APSP remains an open question. A starker contrast is seen regarding SSSP: while static SSSP (in graphs with nonnegative weights) can be solved in O(m+nlog⁡n)O(m + n \log n) time via Dijkstra’s algorithm, under the APSP hypothesis, computing decremental SSSP (even single source single destination) for a single edge failure either requires n3−o(1)n^{3-o(1)} preprocessing time, or n2−o(1)n^{2-o(1)} query time [HLNV17]. This gives a substantial gap between the static and sensitivity complexities.

There are, however, also some positive results that support our objective, most notably for APSP itself. In the incremental setting, this is nearly self-evident: upon the insertion of an edge e=(u,v)e = (u,v), the new distance dG∪e(x,y)d_{G\cup e}(x,y) is given by min⁡(dG(x,y),dG(x,u)+w(u,v)+dG(v,y))\min(d_G(x,y), d_G(x,u) + w(u,v) + d_G(v,y)). Thus, any static APSP algorithm trivially serves as an incremental sensitivity oracle with Q=O(1)Q = O(1). The decremental setting is more complex, yet also yields positive results. In weighted graphs, it is conjectured that no algorithm for

The Cost of Changing Edges for Diameter Computation and More

APSP exists which is substantially faster than the O~(nm)\widetilde{O}(nm) time required for running Dijkstra’s algorithm from all nodes. Bernstein and Karger [BK09b] demonstrated that for 1 edge failure decremental APSP one can indeed achieve1 P=O~(nm+n2)P=\widetilde{O}(nm+n^2) and Q=O(1)Q=O(1), giving a preprocessing time that is the same as the best known for APSP.

We provide a brief summary of the results for decremental/incremental diameter and eccentricities that are already known, and compare them with our ideal objective. We focus primarily on the case of single edge sensitivity.

Previous Results for the Decremental Setting: Previous decremental algorithms reduce these problems to Distance Sensitivity Oracles (DSO) or single-source DSOs (with a fixed source ss). A DSO is an oracle for decremental APSP. Formally, after preprocessing, we need to answer queries of the form dG∖e(x,y)d_{G\setminus e}(x,y) for some x,y,ex,y,e. From the previous discussion, we note that establishing such a reduction (at least to the former) is nearly as desirable as reducing to APSP itself. We briefly summarize these existing results.

Given a graph GG, a DSO for GG with preprocessing PP and O(1)O(1) query time implies2:

  1. Unweighted Diameter [BCFS21]: a (1+ε)(1+\varepsilon)-approximate algorithm for decremental diameter with P+O(n2/ε)P+O(n^2/\varepsilon) preprocessing and O(1)O(1) query time for unweighted graphs.

Moreover, an α\alpha-approximate single-source DSO with preprocessing PP and O(1)O(1) query time implies:

  1. Eccentricities [BCC+26]: a 2(1+α)2(1+\alpha)-approximate algorithm for decremental (all-node) eccentricities with PP preprocessing and O(1)O(1) query time.

Combining these reductions with existing DSOs yields various trade-offs for decremental diameter and eccentricities. While Reduction (2) is advantageous because it can be extended to multiple failures, both Reductions (1) and (2) are unsatisfactory for single failures. Specifically, they incur approximation losses even with exact DSOs (i.e., when α=1\alpha=1), and only Reduction (1) maintains a factor below 2—yet it only applies to unweighted graphs.

Previous Results for the Incremental Setting: The incremental setting of the sensitivity problem has received significantly less attention than its decremental counterpart. Henzinger et al. [HLNV17] established the only known lower bound for this setting, which applies specifically to cases where at least ω(log⁡n)\omega(\log n) edges are inserted. Prior to this work, neither algorithms nor lower bounds were known for the incremental single-sensitivity setting concerning diameter, radius, and eccentricities.

Our Results for the Decremental Setting

As a first result, we significantly improve upon the decremental diameter algorithm obtained via Reduction (1) through an improved reduction. The reduction is to DSOs, together with an algorithm capable of computing canonical shortest paths on GG; that is, an algorithm that, for each pair of nodes u,vu,v, selects a shortest path πG(u,v)\pi_G(u,v) such that any subpath of a canonical path is itself a canonical path.

Main Theorem 1. Let GG be a graph (directed or undirected, weighted or unweighted) with nn nodes. Suppose it takes time PP to construct a DSO for GG with query time O(1)O(1), and it takes time TT to compute a set of canonical shortest paths on GG. Then, we can solve the following problems on GG:

(i) decremental diameter with P+T+O~(n2)P+T+\widetilde{O}(n^2) preprocessing and O(1)O(1) query time;

(ii) (1+ε)(1+\varepsilon)-approximate all-node decremental eccentricities with P+T+O~ε(n2log⁡M)P+T+\widetilde{O}_{\varepsilon}(n^2\log M) preprocessing and O(1)O(1) query time, assuming the graph has edge weights in [1..M][1..M].

Approx.SettingPreprocessingReductionDSO Reference
(1+ε)(1+\varepsilon)unweighted, combinatorialO~(nm)\widetilde{O}(nm)Reduction (1)[BK09b]
exactweighted, combinatorialO~(nm)\widetilde{O}(nm)1(i)1(i)[BK09b]
(1+ε)(1+\varepsilon)unweightedO(n2.529)O(n^{2.529})Reduction (1)[KS23]
exactunweightedO(n2.529)O(n^{2.529})1(i)1(i)[KS23]
exactweights in [1…M][1\ldots M]O(Mn2.6865)O(Mn^{2.6865})1(i)1(i)[GR21]
exactweights in [−M…M][-M\ldots M]O(Mn2.8729)O(Mn^{2.8729})1(i)1(i)[GW19, CC20]

Table 1. Comparison between the previously best known decremental diameter algorithms (that only work for the unweighted case) obtained through Reduction (1) of [BCFS21] and the better algorithms obtained through our reduction in Theorem 1(i) (the latter highlighted in yellow). By introducing a (1+ε)(1+\varepsilon) approximation factor, the algorithm from Theorem 1(i) can be extended to all-nodes decremental eccentricities using Theorem 1(ii). For exact eccentricities, an additional O(n2.88)O(n^{2.88}) overhead is incurred via Theorem 1(iii). All listed algorithms have O(1)O(1) query time.

(iii) all-node decremental eccentricities in P+T+O~(n2+(7−ω)/(10−2ω))=P+T+O(n2.88)\mathrm{P}+\mathrm{T}+\widetilde{O}\left(n^{2+(7-\omega)/(10-2\omega)}\right)=\mathrm{P}+\mathrm{T}+O(n^{2.88}) preprocessing and O(1)O(1) query time. Here ω<2.3714\omega<2.3714 is the exponent of square matrix multiplication [ADV+25].3

Theorem 1(i) gives a tight reduction from (exact) decremental diameter to the construction of a DSO. This represents a significant improvement over Reduction (1): it eliminates the (1+ε)(1+\varepsilon)-approximation overhead and generalizes to any possible graph beyond unweighted ones!

We observe that the reductions in Main Theorem 1 are of the strongest possible form: the DSO only needs to work on G itself, without requiring the algorithm to support a broader class (all graphs on the same weight set, for instance). We also remark that the newly added dependence on an algorithm computing canonical shortest paths is not a major drawback, as one can generally expect to compute them in the same time as APSP (see [GR21] for instance) and constructing DSOs is harder than APSP. This dependence in Main Theorem 1 is only because it seems unclear how to frame a general reduction (one that works for any graph) from an algorithm that computes canonical paths to one that merely computes APSP. This remains an interesting question in its own right.

In Theorem 1(ii), we extend this reduction to (all-node) eccentricities with an additional (1+ε)(1+\varepsilon)-approximation. We discuss in Section 2 why a loss in the approximation factor for Theorem 1(ii) is unavoidable; thus, at least we are able to minimize this loss. Finally, Theorem 1(iii) demonstrates that even when pursuing an exact reduction, it is possible to maintain a subcubic runtime. In Table 1 we summarize the runtimes that one achieves by combining Main Theorem 1 with existing DSOs, and compare those achieved through Theorem 1(i) and Reduction (1).

We also achieve our target bounds for decremental diameter in the regime of larger approximation ratios and sparse graphs. The first component enabling these results is a near-linear time algorithm for (1+ε)(1+\varepsilon)-approximating the decremental eccentricity of a single vertex. We develop this algorithm by combining monotonicity-related observations (which we also rely on in Main Theorem 1 in some sense) with the decremental single-source shortest distance oracle of Harada et al. [HKIM24].

Lemma 5.5 (Adapted from [HKIM24]). For any ε>0\varepsilon>0, there is an algorithm for decremental (1+ε)(1+\varepsilon)-approximate eccentricities of a single node in a (directed or undirected) graph with weights in [1…M][1\ldots M] with O~ε(mpolylog⁡M)\widetilde{O}_{\varepsilon}(m\operatorname{polylog}M) preprocessing and O(1)O(1) query time.

Since a 2-approximation of the diameter can be obtained by doubling the eccentricity of an arbitrary vertex (i.e., by routing through it), our result implies that a (2+ε)(2+\varepsilon)-approximation of the decremental diameter can be maintained in near-linear time.

Corollary 1.1. For decremental diameter on weighted (directed or undirected) graphs with edge weights in [1…M][1 \ldots M], there is a (2+ε)(2+\varepsilon)-approximate algorithm with O~ε(mpolylog⁡M)\widetilde{O}_{\varepsilon}(m\operatorname{polylog} M) preprocessing and O(1)O(1) query time.

Corollary 1.1 improves upon all decremental all-node eccentricity algorithms derived from Reduction (2) (there the derived approximation ratio is always at least 2). In terms of complexity, Corollary 1.1 nearly matches the static approximation achieved by computing shortest paths from a single node using Dijkstra’s algorithm and routing all distances through it.

The final approximation range to address lies between 1+ε1+\varepsilon and 2. For static (and thus also decremental) algorithms, a known barrier exists at the 3/23/2 threshold: under SETH, any approximation better than 3/23/2 requires at least O(m2−o(1))O(m^{2-o(1)}) time [RV13]. Consequently, significant effort has been directed toward developing faster algorithms specifically for this 3/23/2 ratio. In the static setting, these approximation algorithms typically follow a specific framework [RV13, CGR16, ACIM99]: they identify a set S⊆VS \subseteq V with a certain ”nice” property, which we define as an (α,β,k)(\alpha,\beta,k)-sample4, run Dijkstra from every s∈Ss \in S, and return the maximum distance found. Furthermore, these methods may introduce a small additive error5. For undirected graphs, we demonstrate that algorithms following this framework can be translated to the decremental setting, provided we have an algorithm for maintaining the decremental eccentricity of a single node.

Main Theorem 2. Let G=(V,E)G=(V,E) be an undirected graph with non-negative edge weights. Further, suppose there is an algorithm to find an (α,β,k)(\alpha,\beta,k)-sample from VV in time TT and an algorithm for single-node (α′,β′)(\alpha',\beta')-approximate decremental eccentricity in GG with PP preprocessing and QQ query time. Then, there is a (αα′,αβ′+β)(\alpha\alpha',\alpha\beta'+\beta)-approximate algorithm for decremental diameter in GG with O(T+P+kmQ)O(T+P+kmQ) preprocessing and O(1)O(1) query time.

Since Lemma 5.5 provides an efficient decremental single-node eccentricity algorithm, we are able to achieve once again our primary objective of translating static diameter algorithms in this regime to the decremental setting. By doing so, the approximation factor grows only by a (1+ε)(1+\varepsilon) factor.

Corollary 1.2. Combining Main Theorem 2 with existing algorithms computing a (α,β,k)(\alpha,\beta,k)-sample and Lemma 5.5, yields the following algorithms for decremental diameter on undirected graphs with weights in [1…M][1\ldots M]:

  • (i) a (3/2+ε,M/2)(3/2+\varepsilon,M/2)-approximation with O~ε(mn1/2polylog⁡M)\widetilde{O}_{\varepsilon}(mn^{1/2}\operatorname{polylog} M) preprocessing and O(1)O(1) query (using [RV13]);

  • (ii) an (3/2+ε)(3/2+\varepsilon)-approximation with O~ε(m3/2polylog⁡M)\widetilde{O}_{\varepsilon}(m^{3/2}\operatorname{polylog} M) preprocessing and O(1)O(1) query (using [CLR+14]);

  • (iii) for any k≥1k\geq1, an (2−1/2k+ε,(1−1/2k)M)(2-1/2^k+\varepsilon,(1-1/2^k)M)-approximation with O~ε(mn1/(k+1)polylog⁡M)\widetilde{O}_{\varepsilon}(mn^{1/(k+1)}\operatorname{polylog} M) preprocessing and O(1)O(1) query (using [CGR16]).

As a final contribution to the decremental setting, we provide improved lower bounds.

Lemma 9.1. We can encode a boolean matrix product in a single instance of decremental diameter and decremental all-nodes eccentricities in unweighted (undirected or directed) graphs such that any (3/2−ε)(3/2-\varepsilon)-approximate algorithm for these problems allows us to read off the solution to the boolean matrix product from O(n2)O(n^2) queries.

Thus, for (3/2−ε)(3/2-\varepsilon)-approximations, we obtain a general nω−o(1)n^{\omega-o(1)} lower bound and an n3−o(1)n^{3-o(1)} lower bound for combinatorial algorithms6, given the Boolean Matrix Multiplication hypothesis which stipulates that it is impossible to solve boolean matrix multiplication in truly subcubic time using a combinatorial algorithm. In the latter case, we improve on the lower bound of [HLNV17], which established a 5/45/4-approximation factor as the barrier for subcubic combinatorial algorithms.

Our Results for the Incremental Setting

Interestingly, the incremental setting tells quite a different story, quickly putting an end to our wishful thinking. Indeed, while we achieved our ideal outcome in the decremental setting by matching the runtime of the static algorithm for both approximate and exact cases, it turns out this is (conditionally) impossible for the incremental setting.

Lower Bounds. Because of this, to properly contextualize our results, we must first introduce our lower bounds, as they establish a new baseline that we aim to match. Our lower bounds are based on the Orthogonal Vectors (OV) Hypothesis, which is implied by the Strong Exponential Time Hypothesis (SETH)[Wil05]. It claims that determining whether a set of nn boolean vectors of dimension ω(log⁡n)\omega(\log n) contains an orthogonal pair cannot be done in runtime n2−εn^{2-\varepsilon} for any constant ε>0\varepsilon> 0.

Lemma 9.2. Assuming the OV hypothesis, for ε,δ>0\varepsilon,\delta> 0, there is no data structure which has both O(m2−δ)O(m^{2-\delta}) preprocessing time and O(m1−δ)O(m^{1-\delta}) query time for the following incremental problems:

(i) (5/3−ε)(5/3-\varepsilon)-approximate eccentricity of a single node in an unweighted and undirected graph;

(ii) (5/3−ε)(5/3-\varepsilon)-approximate diameter or radius in an unweighted and undirected graph;

(iii) (2−ε)(2-\varepsilon)-approximate eccentricity of a single node or radius of an unweighted and directed graph; and

(iv) (2−ε)(2-\varepsilon)-approximate diameter in an unweighted and directed graph;

The lower bounds (i),(ii) hold even when the input graph is guaranteed to be disconnected.

We next detail four stark contrasts highlighted by Lemma 9.2, making it far more interesting than a simple baseline to match:

(a) The first contrast lies between the incremental and static settings. While any (3/2−ε)(3/2-\varepsilon)-approximation requires m2−o(1)m^{2-o(1)} time in the static setting, this lower-bound threshold increases from 3/23/2 to 5/35/3 for undirected graphs, and to 22 for directed graphs in the incremental setting.

(b) As mentioned earlier, because we match the decremental setting to the static setting in this paper, the previous point immediately yields a contrast between the incremental and decremental settings, showing that the latter is easier. This asymmetry is somewhat unexpected; as noted for APSP, obtaining an incremental oracle is significantly easier than a decremental one. (For instance, developing a DSO with a preprocessing time that directly matches Williams’ APSP time [Wil14], or simply achieving an o(n3)o(n^3) runtime, remains an interesting open problem, whereas this is easily achievable in the incremental setting.)

(c) Our next contrast relies on the fact that we obtain different lower bounds for directed and undirected graphs. Together with our upper bound, these results show a provable separation between such graph classes. We highlight that such a separation is still a big open problem in the static setting. Indeed there, a lower bound tradeoff for directed graphs has been extended to undirected graphs with substantially more work [DW21, DLV25]. However, from the upper bound side our best algorithm for directed graphs [ADLV23] is quite far from the undirected case [CGR16].

References

  1. [1]D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167–1181, 1999. arXiv:https://doi.org/10.1137/S0097539796303421, doi:10.1137/S0097539796303421. 1, 4
  2. [2]Amir Abboud, Martin Farach-Colton, Ray Li, and Virginia Vassilevska Williams. On diameter approximation in directed graphs. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Gregorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 2:1–2:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.ESA.2023.2, doi:10.4230/LIPIcs.ESA.2023.2. 5
  3. [3]Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2005–2039. SIAM, 2025. 3, 18, 46, 47arxiv.org/abs/2404.16349
  4. [4]Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and Hardness for Diameter in Dynamic Graphs. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.13, doi:10.4230/LIPIcs.ICALP.2019.13. 1DOI
  5. [5]Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377–391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28, doi:10.1137/1.9781611974331.CH28. 1
  6. [6]Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.22, doi:10.4230/LIPIcs.ICALP.2022.22. 1DOI
  7. [7]Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Fault-tolerant ST-Diameter oracles. Algorithmica, 88(4):56, 2026. doi:10.1007/s00453-026-01399-z. 1, 2DOI
  8. [8]Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Space-Efficient Fault-Tolerant Diameter Oracles. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.18, doi:10.4230/LIPIcs.MFCS.2021.18. 1, 2, 3
  9. [9]Gilad Braunschweig, Shiri Chechik, and David Peleg. Fault tolerant additive spanners. In Martin Charles Golumbic, Michal Stern, Avivit Levy, and Gila Morgenstern, editors, Graph-Theoretic Concepts in Computer Science, pages 206–214, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. 1
  10. [10]Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant reachability for directed graphs. In Yoram Moses, editor, Distributed Computing, pages 528–543, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. 1DOI
  11. [11]Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant subgraph for single source reachability: generic and optimal. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 509–518, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897648. 1DOI
  12. [12]Aaron Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 742–755. SIAM, 2010. doi:10.1137/1.9781611973075.61. 1DOI
  13. [13]Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti. Improved purely additive fault-tolerant spanners. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, pages 167–178, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. 1arxiv.org/abs/1507.00505
  14. [14]Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-tolerant approximate shortest-path trees. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, pages 137–148, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. 1
  15. [15]Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Compact and Fast Sensitivity Oracles for Single-Source Distances. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.13, doi:10.4230/LIPIcs.ESA.2016.13. 1DOI
  16. [16]Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.18, doi:10.4230/LIPIcs.STACS.2016.18. 1DOI
  17. [17]Aaron Bernstein and David R. Karger. Improved distance sensitivity oracles via random sampling. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 34–43. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347087. 10, 15, 18
  18. [18]Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 101–110, New York, NY, USA, 2009. Association for Computing Machinery. doi:10.1145/1536414.1536431. 8DOI
  19. [19]Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 101–110. ACM, 2009. doi:10.1145/1536414.1536431. 1, 2, 3, 10, 13, 18DOI
  20. [20]Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta. Single source distance oracle for planar digraphs avoiding a failed node or link. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 223–232. SIAM, 2012. doi:10.1137/1.9781611973099.20. 1DOI
  21. [21]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, STOC 2018, page 267–280, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3188745.3188950. 1DOI
  22. [22]Shiri Chechik and Sarel Cohen. Distance sensitivity oracles with subcubic preprocessing time and fast query time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 1375–1388, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3357713.3384253. 3DOI
  23. [23]Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + ε)-approximate f-sensitive distance oracles. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1479–1496. SIAM, 2017. 1DOI
  24. [24]Keerti Choudhary and Omer Gold. Extremal distances in directed graphs: Tight spanners and near-optimal approximation algorithms. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 495–514, 2020. doi:10.1137/1.9781611975994.30. 8, 28, 29DOI
  25. [25]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, SODA ’16, page 363–376, USA, 2016. Society for Industrial and Applied Mathematics. 4, 5, 24
  26. [26]Keerti Choudhary. An Optimal Dual Fault Tolerant Reachability Oracle. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 130:1–130:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.130, doi:10.4230/LIPIcs.ICALP.2016.130. 1DOI
  27. [27]Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1041–1052. SIAM, 2014. doi:10.1137/1.9781611973402.78. 1, 4, 12, 24, 29, 36DOI
  28. [28]Shiri Chechik and Tianyi Zhang. Nearly optimal approximate dual-failure replacement paths. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 2568–2596. SIAM, 2024. doi:10.1137/1.9781611977912.91. 1DOI
  29. [29]Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. Hardness of approximate diameter: Now for undirected graphs. J. ACM, 72(1), January 2025. doi:10.1145/3704631. 5DOI
  30. [30]Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. pages 384–391, 01 2009. doi:10.1145/1496770.1496813. 13, 45DOI
  31. [31]Ran Duan and Seth Pettie. Connectivity oracles for failure prone graphs. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 465–474, New York, NY, USA, 2010. Association for Computing Machinery. doi:10.1145/1806689.1806754. 1DOI
  32. [32]Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures. SIAM J. Comput., 49(6):1363–1396, 2020. doi:10.1137/17M1146610. 1DOI
  33. [33]Mina Dalirrooyfard and Nicole Wein. Tight conditional lower bounds for approximating diameter in directed graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1697–1710, 2021. 5arxiv.org/abs/2011.03892
  34. [34]Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^{2.5794}M) Time. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 76:1–76:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.76, doi:10.4230/LIPIcs.ICALP.2021.76. 3DOI
  35. [35]Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. FOCS ’12, page 748–757, USA, 2012. IEEE Computer Society. doi:10.1109/FOCS.2012.17. 1DOI
  36. [36]Fabrizio Grandoni and Virginia Vassilevska Williams. Faster replacement paths and distance sensitivity oracles. ACM Trans. Algorithms, 16(1), December 2019. doi:10.1145/3365835. 3DOI
  37. [37]Kaito Harada, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. A nearly linear time construction of approximate single-source distance sensitivity oracles. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, volume 308 of LIPIcs, pages 65:1–65:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.ESA.2024.65, doi:10.4230/LIPICS.ESA.2024.65. 1, 3, 20, 21, 22, 24
  38. [38]Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.26, doi:10.4230/LIPIcs.ITCS.2017.26. 1, 2, 5DOI
  39. [39]Monika Henzinger and Stefan Neumann. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:11, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.48, doi:10.4230/LIPIcs.ESA.2016.48. 1
  40. [40]Neelesh Khanna and Surender Baswana. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs. In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 513–524, Dagstuhl, Germany, 2010. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2481, doi:10.4230/LIPIcs.STACS.2010.2481. 1
  41. [41]Yael Kirkpatrick, Liam Roditty, Richard Qi, and Virginia Vassilevska Williams. New Diameter Approximations via Distance Oracle Techniques. In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of Leibniz International Proceedings in Informatics (LIPIcs), pages 127:1–127:22, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.127, doi:10.4230/LIPIcs.ICALP.2026.127. 8
  42. [42]Adam Karczmarz and Piotr Sankowski. Sensitivity and dynamic distance oracles via generic matrices and frobenius norm. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1745–1756, 2023. doi:10.1109/FOCS57990.2023.00106. 3
  43. [43]Merav Parter. Dual failure resilient bfs structure. Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015. URL: https://api.semanticscholar.org/CorpusID:6923325. 1
  44. [44]Merav Parter and David Peleg. Fault-tolerant approximate BFS structures. ACM Trans. Algorithms, 14(1):10:1–10:15, 2018. doi:10.1145/3022730. 1DOI
  45. [45]Mihai Patrascu and Mikkel Thorup. Planning for fast connectivity updates. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07, page 263–271, USA, 2007. IEEE Computer Society. doi:10.1109/FOCS.2007.54. 1
  46. [46]Hanlin Ren. Improved distance sensitivity oracles with subcubic preprocessing time. J. Comput. Syst. Sci., 123:159–170, 2022. URL: https://doi.org/10.1016/j.jcss.2021.08.005, doi:10.1016/J.JCSS.2021.08.005. 2
  47. [47]Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 261–272. Springer, 2005. 8
  48. [48]Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 515–524, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488673. 1, 4, 24
  49. [49]Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 605–614, 1999. doi:10.1109/SFFCS.1999.814635. 34
  50. [50]Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357–365, 2005. 5DOI
  51. [51]Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 664–673, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2591796.2591811. 5DOI

Paper details

vlnc:W_87sde5a2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents