Pith. sign in

REVIEW 2 major objections 5 minor 243 references

Approximate Single Source Dual Fault Tolerant Distance Oracle

T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims a first single-source dual-fault distance oracle with subquadratic space and polylog query time, within a (1+O(ε)) approximation factor.

desk verdict The SDO(2) construction is genuinely new and the warm-up is solid, but Theorem 1.1 rests on Lemma 7.5, which is used in a case where its key premise is false. read the letter →

arxiv 2607.02999 v2 pith:45OXNHJZ submitted 2026-07-03 cs.DS

Koustav Das , Manoj Gupta This is my paper
classification cs.DS MSC 68P0568W2568R10
keywords faulttolerantdistanceoraclesinglesourcedualedgefailuressubquadraticspaceapproximateshortestpathsdetourdecomposable
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims the first approximate single-source distance oracle for two simultaneous edge failures that breaks the quadratic-space barrier. For an undirected weighted graph with a fixed source, it builds a data structure that fits in O~(n√n) space and answers, for any destination and any set of at most two faulty edges, a (1+O(ε))-approximation of the shortest path that avoids those faults, in polylogarithmic time. The construction stores, for each destination, a compact tree of candidate paths — segment children that bypass a segment of the shortest path and detour children that capture replacement paths — and represents long path pieces implicitly through sampled shortest-path trees. If the central claim is correct, the long-standing open problem of extending single-fault (1+ε)-oracles to multiple faults has a first positive instance in the two-fault single-source case.

What carries the argument

The load-bearing object is the fault-tree FT(st) with its two child types: segment children, which store the shortest 2-decomposable path bypassing a whole segment of the parent path, and detour children, which are replacement paths whose detour starts on a designated segment and rejoins the parent path below it. The companion mechanisms are netpoints and segments, which keep every segment short relative to the path, and random landmark sampling, which stores longest-shortest-path subpieces implicitly in O(1) space per node via shortest-path trees. Together they let the oracle reconstruct candidate paths in polylog time without quadratic storage.

What would settle it

Construct a weighted graph with two faulty edges arranged as in §7.2.2 Case 3 — the single-fault replacement path st⋄e avoids or passes below the segment xy, while the stored 2-decomposable detour P_Ri contains the second faulty edge — and compare (st⋄e)[v',t] with P_Ri[v',t]. Any instance where these tails differ gives a concrete counterexample to Lemma 7.5; then run the full query on that instance and check whether the output ratio exceeds 1+O(ε).

Watch

Extended reading notes

Core claim

The paper's central discovery is a recursive fault-tolerant path tree FT(st) built for each destination t. The root stores the shortest s-t path. For each segment between consecutive geometric netpoints, the construction adds a segment child that bypasses the entire segment and detour children whose detours start on that segment and have bounded length; in the two-fault version the recursion goes two levels and stores 1- and 2-decomposable candidate paths. The authors prove that every primary path in the tree is 2-decomposable — at most three shortest-path pieces joined by at most two edges — and store such paths in O(√n) space per tree by sampling landmarks, so all n trees occupy O~(n√n). Q

Load-bearing premise

The argument stands or falls on Lemma 7.5, which equates the tail of the single-fault replacement path with the tail of the stored detour under the assumption that the replacement path's detour begins above the faulty segment; in the hardest case, that assumption is exactly the one being ruled out, so the equality is unproved.

Editorial extensions

If this is right

  • Breaks the Ω(n²) space barrier that held for (1+ε)-approximate distance oracles handling multiple faults, at least in the single-source two-fault setting.
  • Provides the first SDO(2) with o(n²) space and polylogarithmic query time, where previously only single-fault oracles achieved that combination.
  • If correct, the construction shows that two simultaneous link failures can be handled with nearly the same space as the single-source no-fault distance table, up to poly-log factors.
  • The FT(st) recursion with 2-decomposable paths gives a concrete space/query/approximation trade-off template for replacement-path data structures.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof gap in §7.2.2 Case 3 is the only place where the claimed space-query-approximation trade-off rests on an unverified equality; a repair there would complete the theorem, whereas a counterexample would leave only a weaker guarantee for that case.
  • The 3-fault obstruction described in the conclusion suggests the method could extend to any constant number of faults if one could precompute detours that start between two faulty edges lying on the same segment — a 'middle detour' primitive.
  • A natural stress test would compute the exact approximation ratio on random small graphs with adversarially placed fault pairs, comparing the oracle's output to the true replacement path; systematic violations localized to Case 3 would reveal exactly where the unproved lemma breaks.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes the first single-source dual-fault distance oracle (SDO(2)) with subquadratic space, claiming O(n√n log^4_{1+ε} nW) space and O(log^{O(1)}_{1+ε} nW) query time for undirected weighted graphs, returning (1+O(ε))-approximate distances from a fixed source s to any t while avoiding up to two failed edges. The construction adapts the all-pairs FT data structure of Chechik et al. [CCFK17] to the single-source setting by building an FT(st) tree for each destination t, using 1- and 2-decomposable paths, netpoints/segments, random sampling, and LCA-based path membership checks. The single-fault warm-up section (Section 4) is largely coherent and introduces a reusable approximation lemma (Lemma 4.6). The dual-fault extension (Sections 5–7) adds level-1 and level-2 detour children and a recursive query algorithm QUERYDUAL/QUERYDETOUR. The main correctness proof for the hardest dual-fault case is in §7.2.2.

Significance. If the main theorem were established, it would be a notable breakthrough: prior approximate oracles handling multiple faults required Ω(n^2) space, and this paper would give the first o(n^2)-space SDO(2) with near-constant query time. The paper also contributes an explicit, modular construction, a clean single-fault oracle, and a generally useful approximation lemma (Lemma 4.6). The space analysis via sparse sampling and LCA-based path representation is plausible. However, the central dual-fault correctness proof contains a load-bearing flaw in the hardest case (§7.2.2, Lemma 7.5 and its application in Case 3), so the claimed Theorem 1.1 is not established by the submitted text. The rejection is due to this mathematical gap, not to disagreement with the community's open questions or to stylistic issues.

major comments (2)
  1. [§7.2.2, Lemma 7.5] The proof of Lemma 7.5 relies on the assertion that 'the detour of st⋄e starts above the segment xy'. This is used to conclude that the subpath (st⋄e)[s,v'] avoids {e1,e2}, and hence to derive a uniqueness-of-shortest-paths contradiction. But §7.2.2 is introduced precisely as the case where st⋄e does NOT intersect xy above e; it either intersects xy below e or avoids the whole segment xy. Therefore the premise is false in exactly the context where Lemma 7.5 is applied. Consequently, the claimed equality (st⋄e)[v',t] = P_Ri[v',t] is unproved. Without this equality, the chain in Case 3 — namely R[z,t] = (st⋄e)[z,t] and (st⋄e)[v',t] = P_Ri[v',t], hence R[z,t] = P_Ri[z,t] — collapses, and the subsequent application of Lemma 4.6 has no basis. The (1+k5ε)-approximation for Case 3, and therefore for Theorem 1.1, is unsupported.
  2. [§7.2.2, Lemma 7.5 proof (second paragraph)] Even reading the lemma's proof charitably, there is an internal contradiction. The proof assumes for contradiction that the edge e2 lies on the subpath (st⋄e)[v',t]. It then states that 'st⋄e is the shortest path avoiding {e1,e2,e}'. But if e2 lies on (st⋄e)[v',t], then st⋄e contains e2 and therefore does not avoid {e1,e2}. The statement is impossible under the assumption. This is not a minor gap: the contradiction that the proof seeks to derive rests on a claim that cannot hold in the very scenario being considered. The lemma as stated is therefore not proven; it is unclear whether it is true.
minor comments (5)
  1. [Section 8] The paper itself admits that 'our analysis does not account for preprocessing time'. Since the result is advertised as a distance oracle with space and query-time guarantees, a complete data-structure theorem should either include a preprocessing bound or explicitly state that preprocessing time is not addressed. This is not the central issue, but it should be fixed in any revision.
  2. [Abstract and Introduction] The abstract states that 'all (1+ε)-approximate distance oracles that handle multiple faults require Ω(n^2) space'. This conflates all-pairs DO(f) with single-source SDO(f); the paper itself cites SDO(1) constructions with o(n^2) space ([BK13], [BCHR20]). The claim should be qualified to all-pairs oracles or to f≥2 in the single-source setting.
  3. [Throughout] There are numerous numbering inconsistencies: Lemma 2.5 is sometimes referred to as 'Theorem 2.5'; Lemma 4.6 is called 'Theorem 4.6'; Lemmas 4.7–4.9 are referred to as 'Theorem 4.7/4.8'. The definitions in Section 2 are sometimes labeled 'Theorem 2.7'/'Theorem 2.8' although they are definitions. These should be harmonized.
  4. [Algorithm 3] The pseudocode of MAKENODE for level-2 nodes is hard to follow: the indentation and the use of DETSEGMENT are not fully formal, and the 'gray' highlights mentioned in the text are not visible. The recursion when DETSEGMENT(R) is nonempty should be stated as explicit pseudocode rather than a prose description.
  5. [Section 4.5.2 and Section 7.1] The proof of Lemma 4.8 uses the inequality |zv| ≤ |zt| with a netpoint argument. The presentation is somewhat cryptic and Figure 4 is not referenced precisely in the text. This is a minor clarity issue; the lemma itself appears plausible in the single-fault setting.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the SDO(2) derivation is built on external lemmas and explicit case analysis; the flagged Lemma 7.5 problem is a correctness gap, not a circular reduction.

full rationale

The paper's central derivation is not circular. The space and query bounds follow from an explicit construction: FT(st) has O(log^4 nW) nodes, each stored in Õ(√n) space using sampled shortest-path trees and LCA queries, relying on external Lemma 2.2 (ABK+02), Lemma 2.5 (CCFK17, reproved in Appendix A), and the Bender–Farach-Colton LCA structure (BF00). Query correctness is argued by induction over affected vertices with a case analysis; the reported approximation is proved from the construction, not assumed. The only self-citation, [GS18], appears in related work and in the standard uniqueness assumption; it is not load-bearing. The serious weakness is a proof gap, not circularity: in §7.2.2 Case 3, Lemma 7.5 concludes (st⋄e)[v',t] = P_Ri[v',t] using the assertion 'the detour of st⋄e starts above the segment xy', even though that subsection is exactly the case where st⋄e intersects xy below e or avoids the whole segment xy. Section 8 also concedes that preprocessing time is unaccounted for. These are correctness/completeness concerns outside the circularity rubric; no prediction is equivalent to its input by construction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central proof rests on standard shortest-path decomposition lemmas, the netpoint/segment framework from CCFK17, a uniqueness-of-shortest-paths assumption, and the random sampling method. No new entities, forces, or fitted constants are introduced; the free parameters are the user-specified ε and the sampling probability.

free parameters (2)
  • ε (approximation accuracy) = given as input
    Standard approximation parameter, not fitted to data; used throughout to define netpoints, segments, and detour length thresholds.
  • random sampling probability p = Õ(1/√n)
    Chosen so that |L| = Õ(√n) and every stored shortest-path subpath with ≥√n edges contains a sampled vertex with high probability. This is a design choice balancing space and coverage, not a fitted value.
assumptions (4)
  • domain assumption The shortest path between any pair of vertices is unique, even in the presence of edge failures.
    Stated in §2 and ensured by infinitesimal weight perturbation. Used in Lemma 7.4, Lemma 7.5, and elsewhere to conclude that two candidate paths must coincide.
  • standard math After k edge failures, each new shortest path is k-decomposable (Lemma 2.2, [ABK+02]).
    Cited background theorem underlying the 2-decomposable path representation of all stored primary paths.
  • standard math Segment length bound (Lemma 2.5, [CCFK17]): for an edge e on a path P, seg(e,P) is either {e} or has length ≤ ε·min{|P[s,u]|,|P[u,t]|} ≤ ε|P|.
    Cited lemma, proved in Appendix A; used to bound the error introduced by replacing subpaths with segments in the approximation analysis.
  • standard math A random sample of Õ(√n) vertices hits every one of O(n polylog n) fixed paths of length ≥√n with high probability.
    Implicit in §4.1; relies on the standard union bound over the deterministic collection of stored paths and the independence of the sampling.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximate Single Source Dual Fault Tolerant Distance Oracle." pith.science (2026). https://pith.science/paper/45OXNHJZ

@misc{pith2026260702999,
  author       = {Pith},
  title        = {Pith review of: Approximate Single Source Dual Fault Tolerant Distance Oracle},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/45OXNHJZ}},
  note         = {Machine review of arXiv:2607.02999}
}
abstract

We are given an undirected weighted graph $G$ with $n$ vertices and $m$ edges, edge weights in $[1, W]$, and a designated source vertex $s$. We design a single source dual fault tolerant distance oracle for $G$. Given a destination vertex $t$ and a set $F$ of at most two faulty edges, the oracle returns a $(1 + O(\epsilon))$-approximation of the weight of the shortest path from the source $s$ to $t$ avoiding $F$. Our oracle uses $\tilde{O}(n\sqrt{n})$ space and has $\tilde{O}(1)$ query time. Prior to our result, single source single fault tolerant oracles were known to return a $(1+\epsilon)$ approximation of the weight of the shortest path using $\tilde{O}(n)$ space and $O(1)$ query time. However, extending these approaches to multiple faults remained an open problem. Indeed, all $(1+\epsilon)$-approximate distance oracles that handle multiple faults require $\Omega(n^2)$ space. We break this bound by presenting the first dual fault tolerant distance oracle with $o(n^2)$ space.

Figures

Figures reproduced from arXiv: 2607.02999 by the authors.

Figure 1
Figure 1. Netpoints originating from the vertex s are shown in red and form the set L. Netpoints originating from the vertex t are shown in blue and form the set R. A vertex may belong to both L and R. The union of these sets constitutes the set of netpoints. Definition 2.4 (Segment). A segment of a path P is any subpath between two consecutive netpoints on P. For an edge e ∈ P, define seg(e, P) as the unique segment in P tha… view at source ↗
Figure 2
Figure 2. Let P be a path from s to t. Let R be a path (shown in pink) avoiding e that lies on the segment xy. Detour of R is R[w, t]. The detour of R starts on the segment xy above e at w and joins the path at z below the segment xy. Definition 2.7. (Detour of a path R) Let R be a path from s to t that avoids an edge e on the original shortest path st. Let w be the last vertex of R that also lies on PREFIX(st, e), that is, t… view at source ↗
Figure 3
Figure 3. Part 1: st ⋄ e avoids segment xy. Part 2: st ⋄ e intersects xy below e on segment xy. Part 3: st ⋄ e intersects xy above e on segment xy. Lemma 4.6. Let R be a node in FT(st). Let e = (u, v) be the last faulty edge on the path PR with u closer to s. Let S = seg(e, PR ). Suppose the fault tolerant path R = st ⋄ F intersects S at a vertex z below e. Assume there exists a path Q from z to t that also avoids F. If the f… view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: Proving |zv| ⩽ |tz|. We now show that |zv| ⩽ |tz| (See [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: |su ⋄ e| ⩽ |st ⋄ e| For the second part of the lemma, using triangle inequality, we know that , |su ⋄ F| ⩽ |sw ⋄ F| + |wu ⋄ F| (2) = |sw ⋄ F| + |wu| (since wu has no fault) (3) Since R intersects xy above e at a vertex w |st ⋄ F| ⩽ |sw ⋄ F| + |wt ⋄ F| (4) As wu is a su…
Figure 6
Figure 6. Figure 6: Illustration of different types of detours in path [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Different ways st ⋄ F can intersect. Let v ∈ V(F) ∪ {t}. We want to find how many times QUERYDUAL(v, ·) will be called. We claim that this can be called at most 4 times. Indeed as explained during the discussion of QUERYDUAL, every time QUERYDUAL(v, ·) is called, we ar…
Figure 8
Figure 8. Figure 8: st ⋄ F does not intersect pq and the detour starts from xy containing e ′ , the path PXj avoids the entire fault set F. Let r be the vertex in {u, u ′ } that is closest to z (See [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: st ⋄ F intersects pq above e ′ . This case mirrors the above case. While processing Ri, we constructed a 2-decomposable detour child in Yj of Ri such that the detour of PYj starts as high as possible on pq and whose detour length is at most (1 + ε) times that of the de…
Figure 10
Figure 10. Figure 10: st ⋄ F intersects pq below e ′ . Let e ′ = (u ′ , v ′ ), where v ′ lies closer to t on PRi . In Line 5 of QUERYDETOUR, we set PATH = |PRi [v ′ , t]| + QUERYDUAL(v ′ , ROOT(FT(sv′ ))) = |PRi [v ′ , z]| + |PRi [z, t]| + QUERYDUAL(v ′ , ROOT(FT(sv′ ))) 23 [PITH_FULL_IMA…
Figure 11
Figure 11. Figure 11: st ⋄ F when intersect st ⋄ e on the segment pq containing the edge e ′ Proof. Assume for contradiction that R intersects st ⋄ e at z above the second faulty edge e ′ (see Figure 11a) . Then there are two different shortest paths from s to z avoiding F = {e, e ′ }. One…
Figure 12
Figure 12. Figure 12: e2 lies on the (st ⋄ e)[v ′ , t] Assume for contradiction that the edge e2 lies on the subpath (st ⋄ e)[v ′ , t] (See [PITH_FULL_IMAGE:figures/full_fig_p026_12.png]
Figure 13
Figure 13. Figure 13: 3 edge fault case path in the figure). If e1 were absent, the path from z to s along st would suffice to reach s. However, the presence of e1 introduces significant complications. By our assumption, |sz ⋄ F| ≫ |st ⋄ F|, so this detour offers no advantage. In fact, in …
Figure 14
Figure 14. Figure 14: Illustration of subpath decomposition of [PITH_FULL_IMAGE:figures/full_fig_p030_14.png]
Figure 15
Figure 15. Figure 15: The segment endpoints x and y lie in different decomposed paths Qi and Qj, respectively. Since there are log1+ϵ n segments, there can be at most 2 log1+ϵ n segment endpoints. Hence, the total time required for this operation is O(log1+ϵ n). C Proof of the Section 7 We…

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

243 extracted references · 5 linked inside Pith

  1. [1]

    Improved Distance (Sensitivity) Oracles with Subquadratic Space , booktitle =

    Davide Bil. Improved Distance (Sensitivity) Oracles with Subquadratic Space , booktitle =

  2. [2]

    Approximate Distance Sensitivity Oracles in Subquadratic Space , booktitle =

    Davide Bil. Approximate Distance Sensitivity Oracles in Subquadratic Space , booktitle =

  3. [3]

    Incremental Topological Sort and Cycle Detection in Expected Total Time , year =

    Aaron Bernstein and Shiri Chechik , booktitle =. Incremental Topological Sort and Cycle Detection in Expected Total Time , year =

  4. [4]

    An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model , year =

    Surender Baswana and Keerti Choudhary and Liam Roditty , booktitle =. An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model , year =. doi:10.4230/LIPIcs.ICALP.2017.72 , timestamp =

    doi:10.4230/lipics.icalp.2017.72 2017

  5. [5]

    Workshop on Algorithms and Data Structures , pages=

    Faster approximation of distances in graphs , author=. Workshop on Algorithms and Data Structures , pages=. 2007 , organization=

    2007

  6. [6]

    2010 , publisher=

    On the complexity of matrix multiplication , author=. 2010 , publisher=

    2010

  7. [7]

    Algorithmica , volume=

    Faster algorithms for all-pairs small stretch distances in weighted graphs , author=. Algorithmica , volume=. 2012 , publisher=

    2012

  8. [8]

    Nearly 2-Approximate Distance Oracles in Subquadratic Time , booktitle =

    Shiri Chechik and Tianyi Zhang , editor =. Nearly 2-Approximate Distance Oracles in Subquadratic Time , booktitle =

Show all 243 references
  1. [9]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    An almost 2-approximation for all-pairs of shortest paths in subquadratic time , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  2. [10]

    Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35 , pages=

    Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error , author=. Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35 , pages=. 2008 , organization=

    2008

  3. [11]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Faster matrix multiplication via asymmetric hashing , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  4. [12]

    SIAM Journal on Computing , volume=

    Fast estimation of diameter and shortest paths (without matrix multiplication) , author=. SIAM Journal on Computing , volume=. 1999 , publisher=

    1999

  5. [13]

    European Symposium on Algorithms , pages=

    Priority queues: Small, monotone and trans-dichotomous , author=. European Symposium on Algorithms , pages=. 1996 , organization=

    1996

  6. [14]

    SIAM Journal on Computing , volume=

    On RAM priority queues , author=. SIAM Journal on Computing , volume=. 2000 , publisher=

    2000

  7. [15]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    A randomized algorithm for single-source shortest path on undirected real-weighted graphs , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  8. [16]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    Breaking the Sorting Barrier for Directed Single-Source Shortest Paths , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  9. [17]

    International Colloquium on Automata, Languages, and Programming , pages=

    Improved shortest paths on the word RAM , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2000 , organization=

    2000

  10. [18]

    ACM SIGACT News , volume=

    Recent results on the single-source shortest paths problem , author=. ACM SIGACT News , volume=. 1997 , publisher=

    1997

  11. [19]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    New bounds for matrix multiplication: from alpha to omega , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  12. [20]

    TheoretiCS , volume=

    A refined laser method and faster matrix multiplication , author=. TheoretiCS , volume=. 2024 , publisher=

    2024

  13. [21]

    Approximate Distance Sensitivity Oracles in Subquadratic Space , journal =

    Davide Bil. Approximate Distance Sensitivity Oracles in Subquadratic Space , journal =. 2024 , url =. doi:10.46298/THEORETICS.24.15 , timestamp =

    2024 doi

  14. [22]

    Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees , journal =

    Davide Bil. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees , journal =. 2022 , url =. doi:10.1007/S00453-021-00879-8 , timestamp =

    2022 doi

  15. [23]

    Journal of computer and system sciences , volume=

    On the all-pairs-shortest-path problem in unweighted undirected graphs , author=. Journal of computer and system sciences , volume=. 1995 , publisher=

    1995

  16. [24]

    Journal of Algorithms , volume=

    All-pairs small-stretch paths , author=. Journal of Algorithms , volume=. 2001 , publisher=

    2001

  17. [25]

    All-pairs nearly 2-approximate shortest paths in

    Baswana, Surender and Goyal, Vishrut and Sen, Sandeep , journal=. All-pairs nearly 2-approximate shortest paths in. 2009 , publisher=

    2009

  18. [26]

    43rd International Colloquium on Automata, Languages, and Programming,

    Christian Sommer , title =. 43rd International Colloquium on Automata, Languages, and Programming,

  19. [27]

    Compact routing schemes , year =

    Mikkel Thorup and Uri Zwick , booktitle =. Compact routing schemes , year =

  20. [28]

    CoRR , title =

    Aaron Bernstein and Danupon Nanongkai and Christian Wulff. CoRR , title =. 2022 , volume =. doi:10.48550/arXiv.2203.03456 , eprint =

    2022 doi arXiv

  21. [29]

    A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths , year =

  22. [30]

    Dynamic Set Cover: Improved Amortized and Worst-Case Update Time , year =

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai and Xiaowei Wu , booktitle =. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time , year =

  23. [31]

    Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs , year =

    Andr. Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs , year =

  24. [32]

    Information Processing Letters , volume=

    Improved bounds for rectangular monotone min-plus product and applications , author=. Information Processing Letters , volume=. 2023 , publisher=

    2023

  25. [33]

    Fast 2-Approximate All-Pairs Shortest Paths , booktitle =

    Michal Dory and Sebastian Forster and Yael Kirkpatrick and Yasamin Nazari and Virginia. Fast 2-Approximate All-Pairs Shortest Paths , booktitle =

  26. [34]

    New Algorithms for All Pairs Approximate Shortest Paths , booktitle =

    Liam Roditty , editor =. New Algorithms for All Pairs Approximate Shortest Paths , booktitle =

  27. [35]

    Faster Approximate All Pairs Shortest Paths , booktitle =

    Barna Saha and Christopher Ye , editor =. Faster Approximate All Pairs Shortest Paths , booktitle =

  28. [36]

    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , year=

    New additive approximations for shortest paths and cycles , author=. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , year=

    2022

  29. [37]

    SIAM Journal on Computing , volume=

    All-pairs almost shortest paths , author=. SIAM Journal on Computing , volume=. 2000 , publisher=

    2000

  30. [38]

    Distributed weighted min-cut in nearly-optimal time , year =

    Michal Dory and Yuval Efron and Sagnik Mukhopadhyay and Danupon Nanongkai , booktitle =. Distributed weighted min-cut in nearly-optimal time , year =

  31. [39]

    Vertex connectivity in poly-logarithmic max-flows , year =

    Jason Li and Danupon Nanongkai and Debmalya Panigrahi and Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai , booktitle =. Vertex connectivity in poly-logarithmic max-flows , year =

  32. [40]

    A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond , year =

    Julia Chuzhoy and Yu Gao and Jason Li and Danupon Nanongkai and Richard Peng and Thatchaphol Saranurak , booktitle =. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond , year =

  33. [41]

    Weighted min-cut: sequential, cut-query, and streaming algorithms , year =

    Sagnik Mukhopadhyay and Danupon Nanongkai , booktitle =. Weighted min-cut: sequential, cut-query, and streaming algorithms , year =

  34. [42]

    Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary , year =

    Aaron Bernstein and Jan van den Brand and Maximilian Probst Gutenberg and Danupon Nanongkai and Thatchaphol Saranurak and Aaron Sidford and He Sun , journal =. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary , year =. arXiv , bibsource =:2004.08432 , url =

    2004 arXiv

  35. [43]

    Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time , year =

    Jan van den Brand and Danupon Nanongkai , booktitle =. Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time , year =

  36. [44]

    Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds , year =

    Jan van den Brand and Danupon Nanongkai and Thatchaphol Saranurak , booktitle =. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds , year =

  37. [45]

    Distributed exact weighted all-pairs shortest paths in near-linear time , year =

    Aaron Bernstein and Danupon Nanongkai , booktitle =. Distributed exact weighted all-pairs shortest paths in near-linear time , year =

  38. [46]

    Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time , year =

  39. [47]

    A Faster Distributed Single-Source Shortest Paths Algorithm , year =

    Sebastian Forster and Danupon Nanongkai , booktitle =. A Faster Distributed Single-Source Shortest Paths Algorithm , year =

  40. [48]

    Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks , year =

  41. [49]

    Distributed Exact Weighted All-Pairs Shortest Paths in

    Chien. Distributed Exact Weighted All-Pairs Shortest Paths in. 58th. 2017 , editor =

    2017

  42. [50]

    Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time , year =

    Danupon Nanongkai and Thatchaphol Saranurak and Christian Wulff. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time , year =. 58th

  43. [51]

    Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n\(

    Danupon Nanongkai and Thatchaphol Saranurak , booktitle =. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n\(. 2017 , editor =

    2017

  44. [52]

    Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization , year =

  45. [53]

    New deterministic approximation algorithms for fully dynamic matching , year =

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai , booktitle =. New deterministic approximation algorithms for fully dynamic matching , year =

  46. [54]

    Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , booktitle =. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs , year =. doi:10.1007/978-3-662-47672-7\_59 , url =

    doi

  47. [55]

    Tsourakakis , booktitle =

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai and Charalampos E. Tsourakakis , booktitle =. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams , year =

  48. [56]

    Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai and Thatchaphol Saranurak , booktitle =. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , year =

  49. [57]

    Faster Algorithms for Semi-Matching Problems , year =

    Jittat Fakcharoenphol and Bundit Laekhanukit and Danupon Nanongkai , journal =. Faster Algorithms for Semi-Matching Problems , year =

  50. [58]

    Almost-Tight Distributed Minimum Cut Algorithms , year =

    Danupon Nanongkai and Hsin. Almost-Tight Distributed Minimum Cut Algorithms , year =. Distributed Computing - 28th International Symposium,. doi:10.1007/978-3-662-45174-8\_30 , url =

    doi

  51. [59]

    2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=

    Distance oracles beyond the Thorup-Zwick bound , author=. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=. 2010 , organization=

    2010

  52. [60]

    Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

    Approximate distance oracles with improved bounds , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

  53. [61]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Approximate distance oracles with constant query time , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  54. [62]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Approximate distance oracles with improved query time , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  55. [63]

    Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Approximate distance oracles with improved preprocessing time , author=. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2012 , organization=

    2012

  56. [64]

    Additive Spanners and Distance Oracles in Quadratic Time , journal =

    Mathias B. Additive Spanners and Distance Oracles in Quadratic Time , journal =. 2017 , url =. 1704.04473 , timestamp =

    2017 arXiv

  57. [65]

    Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths , year =

    Surender Baswana and Telikepalli Kavitha , booktitle =. Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths , year =. doi:10.1109/FOCS.2006.29 , eventdate =

    2006 doi

  58. [66]

    Theory Comput

    Sayan Bhattacharya and Wolfgang Dvor. Theory Comput. Syst. , title =. 2017 , number =

    2017

  59. [67]

    Weighted dynamic finger in binary search trees , year =

    John Iacono and Stefan Langerman , booktitle =. Weighted dynamic finger in binary search trees , year =. doi:10.1137/1.9781611974331.ch49 , groups =

    doi

  60. [68]

    42nd Annual Symposium on Foundations of Computer Science,

    John Hershberger and Subhash Suri , title =. 42nd Annual Symposium on Foundations of Computer Science,. 2001 , pages =

    2001

  61. [69]

    Distributed Computing - 28th International Symposium,

    Merav Parter , title =. Distributed Computing - 28th International Symposium,. 2014 , pages =

    2014

  62. [70]

    Upper bounds for time-space trade-offs in sorting and selection , year =

    Frederickson, Greg N , journal =. Upper bounds for time-space trade-offs in sorting and selection , year =

  63. [71]

    Upper Bounds for Maximally Greedy Binary Search Trees , year =

    Kyle Fox , booktitle =. Upper Bounds for Maximally Greedy Binary Search Trees , year =

  64. [72]

    Lawrence and Wegman, Mark N

    Carter, J. Lawrence and Wegman, Mark N. , title =. Proceedings of the Ninth Annual ACM Symposium on Theory of Computing , year =. doi:10.1145/800105.803400 , location =

  65. [73]

    Truthful unit-demand auctions with budgets revisited , year =

    Monika Henzinger and Veronika Loitzenbauer , journal =. Truthful unit-demand auctions with budgets revisited , year =

  66. [74]

    Towards polynomial lower bounds for dynamic problems , year =

    Mihai Patrascu , booktitle =. Towards polynomial lower bounds for dynamic problems , year =

  67. [75]

    The State of the Art in Dynamic Graph Algorithms , year =

    Monika Henzinger , booktitle =. The State of the Art in Dynamic Graph Algorithms , year =

  68. [76]

    The Power of Vertex Sparsifiers in Dynamic Graph Algorithms , year =

    Gramoz Goranci and Monika Henzinger and Pan Peng , booktitle =. The Power of Vertex Sparsifiers in Dynamic Graph Algorithms , year =

  69. [77]

    The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree , year =

    Jakub Lacki and Jakub Ocwieja and Marcin Pilipczuk and Piotr Sankowski and Anna Zych , booktitle =. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree , year =

  70. [78]

    The power of deferral: maintaining a constant-competitive steiner tree online , year =

    Albert Gu and Anupam Gupta and Amit Kumar , booktitle =. The power of deferral: maintaining a constant-competitive steiner tree online , year =

  71. [79]

    Bender and Martin Farach

    Michael A. Bender and Martin Farach. The. 2000 , pages =

    2000

  72. [80]

    The k most vital arcs in the shortest path problem , year =

    Malik, Kavindra and Mittal, Ashok K and Gupta, Santosh K , journal =. The k most vital arcs in the shortest path problem , year =

  73. [81]

    The discrepancy method - randomness and complexity , year =

    Bernard Chazelle , publisher =. The discrepancy method - randomness and complexity , year =

  74. [82]

    and Hopcroft, John E

    Aho, Alfred V. and Hopcroft, John E. , publisher =. The Design and Analysis of Computer Algorithms , year =

  75. [83]

    Symbolic algorithms for qualitative analysis of Markov decision processes with B

    Krishnendu Chatterjee and Monika Henzinger and Manas Joglekar and Nisarg Shah , journal =. Symbolic algorithms for qualitative analysis of Markov decision processes with B. 2013 , number =

    2013

  76. [84]

    Subquadratic dynamic path reporting in directed graphs against an adaptive adversary , year =

    Adam Karczmarz and Anish Mukherjee and Piotr Sankowski , booktitle =. Subquadratic dynamic path reporting in directed graphs against an adaptive adversary , year =

  77. [85]

    Ryan , journal =

    Williams, Virginia Vassilevska and Williams, R. Ryan , journal =. Subcubic Equivalences Between Path, Matrix, and Triangle Problems , year =

  78. [86]

    Italiano and Amnon Nissenzweig , journal =

    David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon Nissenzweig , journal =. Sparsification: A technique for speeding up dynamic graph algorithms , year =

  79. [87]

    Sparse Fault-Tolerant

    Merav Parter and David Peleg , booktitle =. Sparse Fault-Tolerant. 2013 , pages =

    2013

  80. [88]

    Space--time trade-offs for stack-based algorithms , year =

    Barba, Luis and Korman, Matias and Langerman, Stefan and Sadakane, Kunihiko and Silveira, Rodrigo I , journal =. Space--time trade-offs for stack-based algorithms , year =

  81. [89]

    Simultaneously Load Balancing for Every p-norm, With Reassignments , year =

    Aaron Bernstein and Tsvi Kopelowitz and Seth Pettie and Ely Porat and Clifford Stein , booktitle =. Simultaneously Load Balancing for Every p-norm, With Reassignments , year =. doi:10.4230/LIPIcs.ITCS.2017.51 , groups =

    2017 doi

  82. [90]

    Simple deterministic algorithms for fully dynamic maximal matching , year =

    Ofer Neiman and Shay Solomon , booktitle =. Simple deterministic algorithms for fully dynamic maximal matching , year =

  83. [91]

    Shortest paths in directed planar graphs with negative lengths: A linear-space O (n log 2 n)-time algorithm , year =

    Klein, Philip N and Mozes, Shay and Weimann, Oren , journal =. Shortest paths in directed planar graphs with negative lengths: A linear-space O (n log 2 n)-time algorithm , year =

  84. [92]

    Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form , year =

    Adam Karczmarz and Piotr Sankowski , booktitle =. Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form , year =

  85. [93]

    Sensitive Distance and Reachability Oracles for Large Batch Updates , year =

    Jan van den Brand and Thatchaphol Saranurak , booktitle =. Sensitive Distance and Reachability Oracles for Large Batch Updates , year =

  86. [94]

    Self-Adjusting Binary Search Trees , year =

    Daniel Dominic Sleator and Robert Endre Tarjan , journal =. Self-Adjusting Binary Search Trees , year =. doi:10.1145/3828.3835 , timestamp =

  87. [95]

    Scaling algorithms for approximate and exact maximum weight matching , year =

    Ran Duan and Seth Pettie and Hsin-Hao Su , journal =. Scaling algorithms for approximate and exact maximum weight matching , year =

  88. [96]

    Distributed Computing , title =

    Yehuda Afek and Anat Bremler. Distributed Computing , title =. 2002 , number =

    2002

  89. [97]

    Replacement paths via fast matrix multiplication , year =

    Weimann, Oren and Yuster, Raphael , booktitle =. Replacement paths via fast matrix multiplication , year =

  90. [98]

    Replacement paths and k simple shortest paths in unweighted directed graphs , year =

    Roditty, Liam and Zwick, Uri , journal =. Replacement paths and k simple shortest paths in unweighted directed graphs , year =

  91. [99]

    Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication , year =

    Weimann, Oren and Yuster, Raphael , journal =. Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication , year =. doi:10.1145/2438645.2438646 , issue_date =

  92. [100]

    Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation , year =

    Monika Rauch Henzinger and Valerie King , journal =. Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation , year =

  93. [101]

    Preserving Distances in Very Faulty Graphs , year =

    Greg Bodwin and Fabrizio Grandoni and Merav Parter and Virginia Vassilevska Williams , booktitle =. Preserving Distances in Very Faulty Graphs , year =

  94. [102]

    Practical Minimum Cut Algorithms , year =

    Monika Henzinger and Alexander Noe and Christian Schulz and Darren Strash , booktitle =. Practical Minimum Cut Algorithms , year =

  95. [103]

    Powers of tensors and fast matrix multiplication , year =

    Fran. Powers of tensors and fast matrix multiplication , year =. International Symposium on Symbolic and Algebraic Computation,

  96. [104]

    Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , year =

    Amir Abboud and Virginia Vassilevska Williams , booktitle =. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , year =

  97. [105]

    Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity , year =

    Jacob Holm and Kristian de Lichtenberg and Mikkel Thorup , journal =. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity , year =

  98. [106]

    Edmonds , journal =

    J. Edmonds , journal =. Paths, trees, and flowers , year =

  99. [107]

    Oracles for Distances Avoiding a Failed Node or Link , year =

    Camil Demetrescu and Mikkel Thorup and Rezaul Alam Chowdhury and Vijaya Ramachandran , journal =. Oracles for Distances Avoiding a Failed Node or Link , year =

  100. [108]

    On the k-simple shortest paths problem in weighted directed graphs , year =

    Roditty, Liam , booktitle =. On the k-simple shortest paths problem in weighted directed graphs , year =

  101. [109]

    Online Bipartite Matching with Amortized Replacements , year =

    Aaron Bernstein and Jacob Holm and Eva Rotenberg , booktitle =. Online Bipartite Matching with Amortized Replacements , year =. doi:10.1137/1.9781611975031.61 , groups =

    doi

  102. [110]

    On Graph Problems in a Semi-streaming Model , year =

    Feigenbaum, Joan and Kannan, Sampath and McGregor, Andrew and Suri, Siddharth and Zhang, Jian , journal =. On Graph Problems in a Semi-streaming Model , year =. doi:10.1016/j.tcs.2005.09.013 , issue_date =

    2005 doi

  103. [111]

    On Dynamic Shortest Paths Problems , year =

    Liam Roditty and Uri Zwick , journal =. On Dynamic Shortest Paths Problems , year =

  104. [112]

    CoRR , title =

    Rapha. CoRR , title =. 2015 , volume =

    2015

  105. [113]

    Journal of computer and system sciences , volume=

    Surpassing the information theoretic bound with fusion trees , author=. Journal of computer and system sciences , volume=. 1993 , publisher=

    1993

  106. [114]

    Edsger Wybe Dijkstra: his life, work, and legacy , editor=

    A note on two problems in connexion with graphs , author=. Edsger Wybe Dijkstra: his life, work, and legacy , editor=. 2022 , publisher=

    2022

  107. [115]

    Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science , pages=

    Trans-dichotomous algorithms for minimum spanning trees and shortest paths , author=. Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science , pages=. 1990 , organization=

    1990

  108. [116]

    New bounds on the complexity of the shortest path problem , year =

    Fredman, Michael L , journal =. New bounds on the complexity of the shortest path problem , year =

  109. [117]

    Accepted in Annual European Symposium on Algorithms, ESA 2021 , title =

    Davide Bil. Accepted in Annual European Symposium on Algorithms, ESA 2021 , title =

    2021

  110. [118]

    Near Optimal Algorithms For The Single Source Replacement Paths Problem , year =

    Shiri Chechik and Sarel Cohen , booktitle =. Near Optimal Algorithms For The Single Source Replacement Paths Problem , year =

  111. [119]

    Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem , year =

    Shiri Chechik and Ofer Magen , booktitle =. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem , year =

  112. [120]

    2022 , address =

    Dey, Dipan and Gupta, Manoj , booktitle =. 2022 , address =. doi:10.4230/LIPIcs.ESA.2022.42 , isbn =

    2022 doi

  113. [121]

    Near Approximation of Maximum Weight Matching through Efficient Weight Reduction , year =

    Andrzej Lingas and Cui Di , booktitle =. Near Approximation of Maximum Weight Matching through Efficient Weight Reduction , year =

  114. [122]

    Multiplying matrices faster than coppersmith-winograd , year =

    Virginia Vassilevska Williams , booktitle =. Multiplying matrices faster than coppersmith-winograd , year =

  115. [123]

    Multiple Source Replacement Path Problem , year =

    Manoj Gupta and Rahul Jain and Nitiksha Modi , booktitle =. Multiple Source Replacement Path Problem , year =

  116. [124]

    Multiple Source Dual Fault Tolerant

    Manoj Gupta and Shahbaz Khan , booktitle =. Multiple Source Dual Fault Tolerant. 2017 , pages =

    2017

  117. [125]

    Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees , year =

    Davide Bil. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees , year =. 33rd Symposium on Theoretical Aspects of Computer Science,

  118. [126]

    More algorithms for all-pairs shortest paths in weighted graphs , year =

    Chan, Timothy M , booktitle =. More algorithms for all-pairs shortest paths in weighted graphs , year =

  119. [127]

    Maximum Matchings via Gaussian Elimination , year =

    Marcin Mucha and Piotr Sankowski , booktitle =. Maximum Matchings via Gaussian Elimination , year =

  120. [128]

    Matrix multiplication via arithmetic progressions , year =

    Coppersmith, Don and Winograd, Shmuel , booktitle =. Matrix multiplication via arithmetic progressions , year =

  121. [129]

    Lovasz and M.D

    L. Lovasz and M.D. Plummer , publisher =. Matching Theory , year =

  122. [130]

    Edmonds and E

    J. Edmonds and E. L. Johnson , journal =. Matching, Euler tours, and the Chinese postman , year =

  123. [131]

    Driscoll and Neil Sarnak and Daniel Dominic Sleator and Robert Endre Tarjan , journal =

    James R. Driscoll and Neil Sarnak and Daniel Dominic Sleator and Robert Endre Tarjan , journal =. Making Data Structures Persistent , year =

  124. [132]

    Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract] , year =

    Aaron Bernstein , booktitle =. Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract] , year =

  125. [133]

    Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs , year =

    Aaron Bernstein , journal =. Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs , year =. doi:10.1137/130938670 , groups =

    doi

  126. [134]

    Maintaining exact distances under multiple edge failures , year =

    Ran Duan and Hanlin Ren , booktitle =. Maintaining exact distances under multiple edge failures , year =. doi:10.1145/3519935.3520002 , timestamp =

  127. [135]

    2012 , address =

    Abhash Anand and Surender Baswana and Manoj Gupta and Sandeep Sen , booktitle =. 2012 , address =. doi:http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.257 , isbn =

    2012 doi

  128. [136]

    Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs , year =

    Abhash Anand and Surender Baswana and Manoj Gupta and Sandeep Sen , journal =. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs , year =

  129. [137]

    Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time , year =

    Manoj Gupta , booktitle =. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time , year =

  130. [138]

    Maintaining a large matching and a small vertex cover , year =

    Krzysztof Onak and Ronitt Rubinfeld , booktitle =. Maintaining a large matching and a small vertex cover , year =

  131. [139]

    Locality in Distributed Graph Algorithms , year =

    Nathan Linial , journal =. Locality in Distributed Graph Algorithms , year =. doi:10.1137/0221015 , timestamp =

    doi

  132. [140]

    Linear programming in the semi-streaming model with application to the maximum matching problem , year =

    Ahn, Kook Jin and Guha, Sudipto , journal =. Linear programming in the semi-streaming model with application to the maximum matching problem , year =

  133. [141]

    Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time , year =

    Gramoz Goranci and Monika Henzinger and Mikkel Thorup , booktitle =. Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time , year =

  134. [142]

    Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning , year =

    Monika Henzinger and Stefan Neumann , booktitle =. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning , year =

  135. [143]

    Improved upper bounds for time-space trade-offs for selection , year =

    Raman, Venkatesh and Ramnath, Sarnath , journal =. Improved upper bounds for time-space trade-offs for selection , year =

  136. [144]

    Improved Space Efficient Algorithms for BFS,

    Niranka Banerjee and Sankardeep Chakraborty and Venkatesh Raman , booktitle =. Improved Space Efficient Algorithms for BFS,. 2016 , pages =

    2016

  137. [145]

    Improved Purely Additive Fault-Tolerant Spanners , year =

    Davide Bil. Improved Purely Additive Fault-Tolerant Spanners , year =. Algorithms -

  138. [146]

    Improved Guarantees for Vertex Sparsification in Planar Graphs , year =

    Gramoz Goranci and Monika Henzinger and Pan Peng , booktitle =. Improved Guarantees for Vertex Sparsification in Planar Graphs , year =

  139. [147]

    Improved Dynamic Reachability Algorithms for Directed Graphs , year =

    Liam Roditty and Uri Zwick , journal =. Improved Dynamic Reachability Algorithms for Directed Graphs , year =

  140. [148]

    Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions , year =

    Aaron Bernstein and Liam Roditty , booktitle =. Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions , year =. doi:10.1137/1.9781611973082.104 , groups =

    doi

  141. [149]

    Improved distance sensitivity oracles with subcubic preprocessing time , year =

    Ren, Hanlin , journal =. Improved distance sensitivity oracles with subcubic preprocessing time , year =

  142. [150]

    Karger , booktitle =

    Aaron Bernstein and David R. Karger , booktitle =. Improved distance sensitivity oracles via random sampling , year =

  143. [151]

    Improved distance sensitivity oracles via fast single-source replacement paths , year =

    Grandoni, Fabrizio and Williams, Virginia Vassilevska , booktitle =. Improved distance sensitivity oracles via fast single-source replacement paths , year =

  144. [152]

    Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components , year =

    Jakub Lacki , journal =. Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components , year =

  145. [153]

    Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths , year =

    Surender Baswana and Ramesh Hariharan and Sandeep Sen , journal =. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths , year =

  146. [154]

    Improved Bounds for Online Preemptive Matching , year =

    Leah Epstein and Asaf Levin and Danny Segev and Oren Weimann , journal =. Improved Bounds for Online Preemptive Matching , year =

  147. [155]

    STACS , title =

    Leah Epstein and Asaf Levin and Juli. STACS , title =. 2010 , pages =

    2010

  148. [156]

    Improved algorithms for the k simple shortest paths and the replacement paths problems , year =

    Gotthilf, Zvi and Lewenstein, Moshe , journal =. Improved algorithms for the k simple shortest paths and the replacement paths problems , year =

  149. [157]

    Implementation and Experimental Analysis of a Dynamic Matching Algorithm and its Variations , year =

    Hemantika Nagpal , journal =. Implementation and Experimental Analysis of a Dynamic Matching Algorithm and its Variations , year =

  150. [158]

    Ullman and Mihalis Yannakakis , booktitle =

    Jeffrey D. Ullman and Mihalis Yannakakis , booktitle =. High-Probability Parallel Transitive Closure Algorithms , year =

  151. [159]

    Graph sketches: sparsification, spanners, and subgraphs , year =

    Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew , booktitle =. Graph sketches: sparsification, spanners, and subgraphs , year =

  152. [160]

    Generic Single Edge Fault Tolerant Exact Distance Oracle , year =

    Manoj Gupta and Aditi Singh , booktitle =. Generic Single Edge Fault Tolerant Exact Distance Oracle , year =

  153. [161]

    Fully dynamic randomized algorithms for graph spanners , year =

    Surender Baswana and Sumeet Khurana and Soumojit Sarkar , journal =. Fully dynamic randomized algorithms for graph spanners , year =

  154. [162]

    Fully-Dynamic Min-Cut , year =

    Mikkel Thorup , journal =. Fully-Dynamic Min-Cut , year =

  155. [163]

    Fully Dynamic Maximal Matching in

    Surender Baswana and Manoj Gupta and Sandeep Sen , journal =. Fully Dynamic Maximal Matching in. 2015 , number =. doi:10.1137/130914140 , timestamp =

    2015 doi

  156. [164]

    Fully Dynamic Matching in Bipartite Graphs , year =

    Aaron Bernstein and Cliff Stein , booktitle =. Fully Dynamic Matching in Bipartite Graphs , year =. doi:10.1007/978-3-662-47672-7_14 , groups =

    doi

  157. [165]

    , booktitle =

    Ivkovic, Zoran and Lloyd, Errol L. , booktitle =. Fully Dynamic Maintenance of Vertex Cover , year =

  158. [166]

    Fully Dynamic Biconnectivity and Transitive Closure , year =

    Monika Rauch Henzinger and Valerie King , booktitle =. Fully Dynamic Biconnectivity and Transitive Closure , year =

  159. [167]

    Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai , booktitle =. Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in. 2017 , editor =

    2017

  160. [168]

    Fully Dynamic Algorithms For Maintaining Approximate Matching In Graphs , year =

    Abhash Anand , school =. Fully Dynamic Algorithms For Maintaining Approximate Matching In Graphs , year =

  161. [169]

    Fully Dynamic (1+ ) -Approximate Matchings , year =

    Manoj Gupta and Richard Peng , booktitle =. Fully Dynamic (1+ ) -Approximate Matchings , year =

  162. [170]

    Finding the most vital node of a shortest path , year =

    Enrico Nardelli and Guido Proietti and Peter Widmayer , journal =. Finding the most vital node of a shortest path , year =

  163. [171]

    Finding the k Shortest Paths , year =

    David Eppstein , booktitle =. Finding the k Shortest Paths , year =

  164. [172]

    Finding Graph Matchings in Data Streams , year =

    Andrew McGregor , booktitle =. Finding Graph Matchings in Data Streams , year =

  165. [173]

    Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time , year =

    Monika Henzinger and Sebastian Krinninger and Veronika Loitzenbauer , booktitle =. Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time , year =

  166. [174]

    Fault tolerant subgraph for single source reachability: generic and optimal , year =

    Surender Baswana and Keerti Choudhary and Liam Roditty , booktitle =. Fault tolerant subgraph for single source reachability: generic and optimal , year =

  167. [175]

    Fault Tolerant Spanners for General Graphs , year =

    Shiri Chechik and Michael Langberg and David Peleg and Liam Roditty , journal =. Fault Tolerant Spanners for General Graphs , year =

  168. [176]

    Fault-tolerant spanners: better and simpler , year =

    Michael Dinitz and Robert Krauthgamer , booktitle =. Fault-tolerant spanners: better and simpler , year =

  169. [177]

    Fault Tolerant Reachability for Directed Graphs , year =

    Surender Baswana and Keerti Choudhary and Liam Roditty , booktitle =. Fault Tolerant Reachability for Directed Graphs , year =

  170. [178]

    Fault-Tolerant Approximate Shortest-Path Trees , year =

    Davide Bil. Fault-Tolerant Approximate Shortest-Path Trees , year =. Algorithms -

  171. [179]

    Fault Tolerant Approximate

    Merav Parter and David Peleg , booktitle =. Fault Tolerant Approximate. 2014 , pages =

    2014

  172. [180]

    Fault tolerant additive and (

    Gilad Braunschvig and Shiri Chechik and David Peleg and Adam Sealfon , journal =. Fault tolerant additive and (. 2015 , pages =

    2015

  173. [181]

    Gabow and Robert Endre Tarjan , journal =

    Harold N. Gabow and Robert Endre Tarjan , journal =. Faster Scaling Algorithms for General Graph-Matching Problems , year =

  174. [182]

    Faster replacement paths and distance sensitivity oracles , year =

    Grandoni, Fabrizio and Williams, Virginia Vassilevska , journal =. Faster replacement paths and distance sensitivity oracles , year =

  175. [183]

    Faster replacement paths , year =

    Williams, Virginia Vassilevska , booktitle =. Faster replacement paths , year =

  176. [184]

    Faster Fully Dynamic Matchings with Small Approximation Ratios , year =

    Aaron Bernstein and Cliff Stein , booktitle =. Faster Fully Dynamic Matchings with Small Approximation Ratios , year =. doi:10.1137/1.9781611974331.ch50 , groups =

    doi

  177. [185]

    Faster dynamic matchings and vertex connectivity , year =

    Piotr Sankowski , booktitle =. Faster dynamic matchings and vertex connectivity , year =

  178. [186]

    Faster all-pairs shortest paths via circuit complexity , year =

    Williams, Ryan , booktitle =. Faster all-pairs shortest paths via circuit complexity , year =

  179. [187]

    Faster, space-efficient selection algorithms in read-only memory for integers , year =

    Chan, Timothy M and Munro, J Ian and Raman, Venkatesh , booktitle =. Faster, space-efficient selection algorithms in read-only memory for integers , year =

  180. [188]

    Efficient Oracles and Routing Schemes for Replacement Paths , year =

    Davide Bil. Efficient Oracles and Routing Schemes for Replacement Paths , year =. 35th Symposium on Theoretical Aspects of Computer Science,

  181. [189]

    Efficient algorithms for maximum weight matchings in general graphs with small edge weights , year =

    Chien-Chung Huang and Telikepalli Kavitha , booktitle =. Efficient algorithms for maximum weight matchings in general graphs with small edge weights , year =

  182. [190]

    Karlin and Kurt Mehlhorn and Friedhelm

    Martin Dietzfelbinger and Anna R. Karlin and Kurt Mehlhorn and Friedhelm. Dynamic Perfect Hashing: Upper and Lower Bounds , year =

  183. [191]

    Kapron and Valerie King and Ben Mountjoy , booktitle =

    Bruce M. Kapron and Valerie King and Ben Mountjoy , booktitle =. Dynamic graph connectivity in polylogarithmic worst case time , year =

  184. [192]

    Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs , year =

    Liam Roditty and Uri Zwick , journal =. Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs , year =

  185. [193]

    Dynamic Algorithms for Graph Coloring , year =

    Sayan Bhattacharya and Deeparnab Chakrabarty and Monika Henzinger and Danupon Nanongkai , booktitle =. Dynamic Algorithms for Graph Coloring , year =

  186. [194]

    Surender Baswana and Shreejit Ray Chaudhury and Keerti Choudhary and Shahbaz Khan , booktitle =. Dynamic. 2016 , pages =

    2016

  187. [195]

    Dual Failure Resilient

    Merav Parter , booktitle =. Dual Failure Resilient. 2015 , pages =

    2015

  188. [196]

    Dual-failure distance and connectivity oracles , year =

    Ran Duan and Seth Pettie , booktitle =. Dual-failure distance and connectivity oracles , year =

  189. [197]

    and Patt-Shamir, B

    Lotker, Z. and Patt-Shamir, B. and Rosen, A. , booktitle =. 2007 , organization =

    2007

  190. [198]

    Distance sensitivity oracles with subcubic preprocessing time and fast query time , year =

    Chechik, Shiri and Cohen, Sarel , booktitle =. Distance sensitivity oracles with subcubic preprocessing time and fast query time , year =

  191. [199]

    Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs , year =

    Aaron Bernstein , booktitle =. Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs , year =. doi:10.4230/LIPIcs.ICALP.2017.44 , groups =

    2017 doi

  192. [200]

    Italiano , booktitle =

    Sayan Bhattacharya and Monika Henzinger and Giuseppe F. Italiano , booktitle =. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching , year =

  193. [201]

    Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in

    Sayan Bhattacharya and Deeparnab Chakrabarty and Monika Henzinger , booktitle =. Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in. 2017 , editor =

    2017

  194. [202]

    Italiano , booktitle =

    Sayan Bhattacharya and Monika Henzinger and Giuseppe F. Italiano , booktitle =. Design of Dynamic Algorithms via Primal-Dual Method , year =

  195. [203]

    Decremental maintenance of strongly connected components , year =

    Liam Roditty , booktitle =. Decremental maintenance of strongly connected components , year =

  196. [204]

    Decremental Approximate-APSP in Directed Graphs , year =

    Aaron Bernstein , booktitle =. Decremental Approximate-APSP in Directed Graphs , year =. doi:10.1007/978-1-4939-2864-4_564 , groups =

    doi

  197. [205]

    , journal =

    Frederickson, G. , journal =. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications , year =

  198. [206]

    Data structures and network algorithms , year =

    Robert Endre Tarjan , publisher =. Data structures and network algorithms , year =

  199. [207]

    Cuckoo hashing , year =

    Rasmus Pagh and Flemming Friche Rodler , journal =. Cuckoo hashing , year =

  200. [208]

    Mirrokni and Cliff Stein , journal =

    Sepehr Assadi and MohammadHossein Bateni and Aaron Bernstein and Vahab S. Mirrokni and Cliff Stein , journal =. Coresets Meet. 2017 , volume =. arXiv , bibsource =:1711.03076 , groups =

    2017 arXiv

  201. [209]

    Constructing a Distance Sensitivity Oracle in

    Yong Gu and Hanlin Ren , booktitle =. Constructing a Distance Sensitivity Oracle in. 2021 , editor =

    2021

  202. [210]

    Conditional Hardness for Sensitivity Problems , year =

    Monika Henzinger and Andrea Lincoln and Stefan Neumann and Virginia Vassilevska Williams , booktitle =. Conditional Hardness for Sensitivity Problems , year =

  203. [211]

    Compact and Fast Sensitivity Oracles for Single-Source Distances , year =

    Davide Bil. Compact and Fast Sensitivity Oracles for Single-Source Distances , year =. 24th Annual European Symposium on Algorithms,

  204. [212]

    Lawler , publisher =

    E. Lawler , publisher =. Combinatorial Optimization: Networks and Matroids , year =

  205. [213]

    Combinatorial optimization: algorithms and complexity , year =

    Christos Papadimitriou and Kenneth Steiglitz , publisher =. Combinatorial optimization: algorithms and complexity , year =

  206. [214]

    Average Case Analysis of Dynamic Graph Algorithms , year =

    David Alberts and Monika Rauch Henzinger , booktitle =. Average Case Analysis of Dynamic Graph Algorithms , year =

  207. [215]

    Average-Case Analysis of Algorithms for Matchings and Related Problems , year =

    Rajeev Motwani , journal =. Average-Case Analysis of Algorithms for Matchings and Related Problems , year =

  208. [216]

    A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , booktitle =. A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths , year =

  209. [217]

    A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths , year =

    Zwick, Uri , booktitle =. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths , year =

  210. [218]

    and Sanders, P

    Pettie, S. and Sanders, P. , journal =. 2004 , number =

    2004

  211. [219]

    A Simple Parallel Algorithm for the Maximal Independent Set Problem , year =

    Luby, M , booktitle =. A Simple Parallel Algorithm for the Maximal Independent Set Problem , year =. doi:10.1145/22145.22146 , isbn =

  212. [220]

    and Hougardy, S

    Drake, D.E. and Hougardy, S. , journal =. 2003 , number =

    2003

  213. [221]

    Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms , year =

    Michal Parnas and Dana Ron , journal =. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms , year =

  214. [222]

    Approximating Maximum Weight Matching in Near-Linear Time , year =

    Duan, Ran and Pettie, Seth , booktitle =. Approximating Maximum Weight Matching in Near-Linear Time , year =. doi:10.1109/FOCS.2010.70 , isbn =

    2010 doi

  215. [223]

    Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs , year =

    Baswana, Surender and Khanna, Neelesh , journal =. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs , year =

  216. [224]

    ACM Transactions on Algorithms (TALG) , volume=

    Approximate single-source fault tolerant shortest path , author=. ACM Transactions on Algorithms (TALG) , volume=. 2020 , publisher=

    2020

  217. [225]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , title =

    Bil. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , title =. 2023 , pages =

    2023

  218. [226]

    An On-Line Edge-Deletion Problem , year =

    Shimon Even and Yossi Shiloach , journal =. An On-Line Edge-Deletion Problem , year =

  219. [227]

    and Vazirani, V.V

    Micali, S. and Vazirani, V.V. , booktitle =. 1980 , organization =

    1980

  220. [228]

    An O (n3loglogn/logn) time algorithm for the all-pairs shortest path problem , year =

    Takaoka, Tadao , journal =. An O (n3loglogn/logn) time algorithm for the all-pairs shortest path problem , year =

  221. [229]

    An O (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path , year =

    Han, Yijie , journal =. An O (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path , year =

  222. [230]

    Hopcroft and Richard M

    John E. Hopcroft and Richard M. Karp , journal =. An n^. 1973 , number =

    1973

  223. [231]

    A nearly optimal oracle for avoiding failed vertices and edges , year =

    Bernstein, Aaron and Karger, David , booktitle =. A nearly optimal oracle for avoiding failed vertices and edges , year =

  224. [232]

    A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs , year =

    Bernstein, Aaron , booktitle =. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs , year =

  225. [233]

    A near-linear-time algorithm for computing replacement paths in planar directed graphs , year =

    Emek, Yuval and Peleg, David and Roditty, Liam , journal =. A near-linear-time algorithm for computing replacement paths in planar directed graphs , year =

  226. [234]

    Analyzing graph structure via linear measurements , year =

    Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew , booktitle =. Analyzing graph structure via linear measurements , year =

  227. [235]

    An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths , year =. arXiv , bibsource =:1504.07056 , url =

    arXiv

  228. [236]

    A more efficient algorithm for the min-plus multiplication , year =

    Dobosiewicz, Wlodzimierz , journal =. A more efficient algorithm for the min-plus multiplication , year =

  229. [237]

    All-pairs shortest paths with real weights in O (n 3/log n) time , year =

    Chan, Timothy M , journal =. All-pairs shortest paths with real weights in O (n 3/log n) time , year =

  230. [238]

    A faster algorithm for the all-pairs shortest path problem and its application , year =

    Takaoka, Tadao , booktitle =. A faster algorithm for the all-pairs shortest path problem and its application , year =

  231. [239]

    Alon, Noga and Babai, L\'. J. Algorithms , title =. 1986 , issn =. doi:10.1016/0196-6774(86)90019-2 , issue_date =

    1986 doi

  232. [240]

    A Fast Algorithm for Finding Dominators in a Flowgraph , year =

    Thomas Lengauer and Robert Endre Tarjan , journal =. A Fast Algorithm for Finding Dominators in a Flowgraph , year =

  233. [241]

    A Data Structure for Dynamic Trees , year =

    Daniel Dominic Sleator and Robert Endre Tarjan , journal =. A Data Structure for Dynamic Trees , year =

  234. [242]

    2017 , pages =

    Shiri Chechik and Sarel Cohen and Amos Fiat and Haim Kaplan , booktitle =. 2017 , pages =

    2017

  235. [243]

    Nearly Optimal Fault Tolerant Distance Oracle , year =

    Dipan Dey and Manoj Gupta , booktitle =. Nearly Optimal Fault Tolerant Distance Oracle , year =. doi:10.1145/3618260.3649697 , timestamp =

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.