pith. sign in

arxiv: 2607.00938 · v1 · pith:JMX3ETJZnew · submitted 2026-07-01 · 💻 cs.DS

Tighter bounds for weighted and unweighted shortest cycle approximation

Avi Kadria , Liam Roditty , Virginia Vassilevska Williams This is my paper

Pith reviewed 2026-07-02 04:39 UTC · model grok-4.3

classification 💻 cs.DS
keywords girth approximationshortest cycleweighted graphsapproximation algorithmsfine-grained lower boundsgraph algorithmsunweighted graphs
0
0 comments X

The pith

For every k≥2, weighted graphs admit a (2k/3)-approximation to girth in Õ(m + n^{1+2/k}) time.

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

The paper establishes that girth approximation algorithms previously known only for unweighted graphs extend to graphs with non-negative real edge weights. For every integer k at least 2, it gives a (2k/3)-approximation running in Õ(m + n^{1+2/k}) time on n-node m-edge weighted graphs. This matches the unweighted trade-off exactly and improves earlier weighted results that achieved the same ratio and time only for selected values of k. The work also supplies new fine-grained lower bounds for girth approximation and related problems on unweighted graphs.

Core claim

The central claim is that the (2k/3)-approximation algorithms and their running times for unweighted graphs extend directly to the weighted case, yielding the first such trade-off that holds for all k ≥ 2 in weighted graphs with non-negative weights.

What carries the argument

Lifting of the unweighted girth approximation techniques to handle non-negative real edge weights without increasing the asymptotic time or worsening the approximation ratio.

Load-bearing premise

The algorithmic techniques developed for unweighted graphs can be lifted to the weighted setting while preserving both the (2k/3) approximation ratio and the stated time bound for every k≥2.

What would settle it

A family of weighted graphs on which every (2k/3)-approximation algorithm for girth requires super-Õ(n^{1+2/k}) time for some fixed k≥2 would falsify the main result.

Figures

Figures reproduced from arXiv: 2607.00938 by Avi Kadria, Liam Roditty, Virginia Vassilevska Williams.

Figure 1
Figure 1. Figure 1: ℓ(C) = g, u ∈ C, (x, y) ∈ C farthest edge from u, (s, t) ∈ C such that (s, t) ∈/ CL(p1(u)) and (s, t) ̸= (x, y). δ(u, t). Wlog, we assume that δ(u,(s, t)) = δ(u, s) + ℓ(s, t) = δ(u, t). Since (s, t) ∈/ CL(p1(u)), it follows from the definition of CL(p1(u)) that δ(A2, t) ≤ δ(p1(u), s) + ℓ(s, t) △ ≤ δ(A1, u) + δ(u, s) + ℓ(s, t) = δ(A1, u) + δ(u, t) (3) Since (s, t) ̸= (x, y) it follows that (s, t) ∈ P(u, x) … view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of hi(C) and h ′ i (C), where C is a shortest cycle in G. 5 Conditional lower bound for (5/3−ϵ)-girth approximation under the Stronger3Sum hypothesis In this section, we show a girth approximation lower bound under the Stronger3Sum hypothesis, which is defined as follows. Hypothesis 8 (Stronger3Sum). There is no O(n 2−ε ) time algorithm for 3Sum on a set A where A ⊆ [±O(n 2 )] and A is a Sidon… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of Theorem 2. The reduction first follows the same steps as the reduction of Theorem 1.14 of [JX23]. Then, we show how to take a small number of subgraphs of the graphs created in the reduction of [JX23] so that if the input set A does not have a non-trivial solution to a + b = c + d then the subgraphs created have no 4-cycles. Moreover, as before, any triangle corresponds to a 3SUM solution, … view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of G′ i,j,k. Proof. From Lemma 22 we have that there is no O(n 3−ε ) time algorithm for ZeroTriangle, such that {ℓ(u, v) | (u, v) ∈ E} is a Sidon set. We show that if there exists an algorithm Alg that solves (4, ρ, T)-AllEdgeCycleListing, for some constant T > 0, in O(n 3−2ρ−ε ) time, then there is an O(n 3−ε ′ ) time algorithm for ZeroTriangle, where {ℓ(u, v) | (u, v) ∈ E} is a Sidon set. Le… view at source ↗
read the original abstract

We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted graphs by Kadria et al. [SODA'22] and Roditty and Trabelsi [arXiv'25] achieve the following trade-off: for every integer $k\geq 2$, there is an $\tilde{O}(n^{1+2/k})$ time algorithm that achieves a $(2k/3)$-approximation for the girth in unweighted $n$-node graphs. The first result of this paper is to achieve the same trade-off for $m$-edge, $n$-node graphs with non-negative real edge weights: a $2k/3$-approximation algorithm running in $\tilde{O}(m+n^{1+2/k})$ time. The dependence on $m$ is unavoidable in weighted graphs. Our result improves on the work of Kadria et al.~[SODA'23] and Ducoffe [ICALP'19 and SIDMA'21], who were only able to achieve such a trade-off for some values of $k$. We also prove new fine-grained lower bounds for girth approximation and related problems in unweighted graphs.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The manuscript extends the (2k/3)-approximation for girth from unweighted graphs to m-edge n-node weighted graphs with non-negative real edge weights, achieving the same Õ(m + n^{1+2/k}) time bound for every integer k ≥ 2. This improves on prior partial results (Kadria et al. SODA'23; Ducoffe ICALP'19/SIDMA'21) that obtained the trade-off only for selected k. The paper also establishes new fine-grained lower bounds for girth approximation and related problems in the unweighted setting.

Significance. If the lifting of the unweighted techniques succeeds without degrading the ratio or introducing extra factors in the weighted case, the result completes the known approximation-time trade-off for weighted girth and removes the previous restriction to selected k. The lower bounds add to the fine-grained complexity landscape. The explicit handling of real weights and the unavoidable m-term are correctly identified as necessary.

minor comments (2)
  1. [Abstract] Abstract: the lower-bound contribution is mentioned only in passing; a one-sentence characterization of the new lower bounds (e.g., which problems and which exponents) would make the abstract self-contained.
  2. The dependence on m is stated to be unavoidable, but no explicit reduction or citation is given in the provided abstract; a pointer to the relevant section or prior reference would strengthen the claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and for recommending minor revision. The referee's summary correctly reflects our main results: extending the (2k/3)-approximation for girth to weighted graphs with non-negative real weights in Õ(m + n^{1+2/k}) time for all k ≥ 2, improving on prior partial results, along with new fine-grained lower bounds in the unweighted setting. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claim is a new algorithmic construction that lifts the (2k/3)-approximation and Õ(m + n^{1+2/k}) time bound from unweighted graphs (cited from prior work) to weighted graphs with non-negative real weights. The abstract presents this extension as the contribution, improving on earlier partial results for only some k. No equations, definitions, or steps in the provided text reduce a claimed prediction or ratio to a fitted parameter or self-referential input by construction. Self-citations to overlapping-author prior work support only the unweighted base case and are not load-bearing for the weighted lifting, which is described as an independent algorithmic advance. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the work relies on standard graph-theoretic assumptions and prior algorithmic techniques without introducing new fitted parameters or postulated entities.

axioms (1)
  • domain assumption Graphs are undirected with non-negative real edge weights.
    Stated explicitly in the abstract when describing the weighted result.

pith-pipeline@v0.9.1-grok · 5757 in / 1263 out tokens · 27754 ms · 2026-07-02T04:39:26.453808+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

141 extracted references · 98 canonical work pages · 3 internal anchors

  1. [1]

    Finding and Counting Given Length Cycles

    Noga Alon and Raphy Yuster and Uri Zwick. Finding and Counting Given Length Cycles. Algorithmica. 1997

    1997

  2. [2]

    Seth Pettie , title =. Theor. Comput. Sci. , volume =

  3. [3]

    Raphael Yuster and Uri Zwick , title =

  4. [4]

    Finding even cycles faster via capped k -walks , booktitle = stoc17, pages =

    S. Finding even cycles faster via capped k -walks , booktitle = stoc17, pages =. 2017 , url =. doi:10.1145/3055399.3055459 , timestamp =

    work page doi:10.1145/3055399.3055459 2017

  5. [5]

    New Subquadratic Approximation Algorithms for the Girth , journal =

    S. New Subquadratic Approximation Algorithms for the Girth , journal =. 2017 , url =

    2017

  6. [6]

    Optimal Girth Approximation for Dense Directed Graphs , booktitle =

    Shiri Chechik and Gur Lifshitz , editor =. Optimal Girth Approximation for Dense Directed Graphs , booktitle =

  7. [7]

    Graph pattern detection: hardness for all induced patterns and faster non-induced cycles , booktitle =

    Mina Dalirrooyfard and Thuy Duong. Graph pattern detection: hardness for all induced patterns and faster non-induced cycles , booktitle =

  8. [8]

    Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph , booktitle = icalp20, series =

    Mina Dalirrooyfard and Virginia. Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph , booktitle = icalp20, series =. 2020 , url =. doi:10.4230/LIPIcs.ICALP.2020.35 , timestamp =

    work page doi:10.4230/lipics.icalp.2020.35 2020

  9. [9]

    Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles , booktitle =

    Mina Dalirrooyfard and Ce Jin and Virginia. Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles , booktitle =

  10. [10]

    Detecting short directed cycles using rectangular matrix multiplication and dynamic programming , booktitle =

    Raphael Yuster and Uri Zwick , editor =. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming , booktitle =

  11. [11]

    A Refined Laser Method and Faster Matrix Multiplication , booktitle =

    Josh Alman and Virginia. A Refined Laser Method and Faster Matrix Multiplication , booktitle =

  12. [12]

    Proceedings of the International Congress of Mathematicians

    Virginia. Proceedings of the International Congress of Mathematicians

  13. [13]

    Ryan Williams , title =

    R. Ryan Williams , title =

  14. [14]

    1978 , url =

    Alon Itai and Michael Rodeh , title =. 1978 , url =. doi:10.1137/0207033 , timestamp =

    work page doi:10.1137/0207033 1978

  15. [15]

    Efficient approximation algorithms for shortest cycles in undirected graphs , journal =

    Andrzej Lingas and Eva. Efficient approximation algorithms for shortest cycles in undirected graphs , journal =. 2009 , url =. doi:10.1016/j.ipl.2009.01.008 , timestamp =

    work page doi:10.1016/j.ipl.2009.01.008 2009

  16. [16]

    Liu and Omer Rotem and Aaron Sidford , title =

    Shiri Chechik and Yang P. Liu and Omer Rotem and Aaron Sidford , title =. Proccedings of the 52nd Annual

  17. [17]

    Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners , booktitle =

    Jakub Pachocki and Liam Roditty and Aaron Sidford and Roei Tov and Virginia. Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners , booktitle =. 2018 , url =. doi:10.1137/1.9781611975031.91 , timestamp =

    work page doi:10.1137/1.9781611975031.91 2018

  18. [18]

    2013 , url =

    Liam Roditty and Roei Tov , title =. 2013 , url =. doi:10.1145/2438645.2438647 , timestamp =

    work page doi:10.1145/2438645.2438647 2013

  19. [19]

    Subquadratic time approximation algorithms for the girth , booktitle =

    Liam Roditty and Virginia. Subquadratic time approximation algorithms for the girth , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.67 , timestamp =

    work page doi:10.1137/1.9781611973099.67 2012

  20. [20]

    Bondy and Miklós Simonovits , title =

    John A. Bondy and Miklós Simonovits , title =. Journal of Combinatorial Theory , pages =

  21. [21]

    Subcubic Equivalences Between Path, Matrix, and Triangle Problems , journal =

    Virginia. Subcubic Equivalences Between Path, Matrix, and Triangle Problems , journal =. 2018 , url =. doi:10.1145/3186893 , timestamp =

    work page doi:10.1145/3186893 2018

  22. [22]

    Towards polynomial lower bounds for dynamic problems , booktitle =

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

  23. [23]

    Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs , booktitle =

    Guillaume Ducoffe , editor =. Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.ICALP.2019.49 , timestamp =

    work page doi:10.4230/lipics.icalp.2019.49 2019

  24. [24]

    Approximate distance oracles , booktitle =

    Mikkel Thorup and Uri Zwick , editor =. Approximate distance oracles , booktitle =. 2001 , url =. doi:10.1145/380752.380798 , timestamp =

    work page doi:10.1145/380752.380798 2001

  25. [25]

    Goldberg and Renato Fonseca F

    Shiri Chechik , editor =. Improved Distance Oracles and Spanners for Vertex-Labeled Graphs , booktitle =. 2012 , url =. doi:10.1007/978-3-642-33090-2\_29 , timestamp =

    work page doi:10.1007/978-3-642-33090-2 2012

  26. [26]

    CoRR , volume =

    Greg Bodwin and Gary Hoppenworth , title =. CoRR , volume =. 2022 , url =. doi:10.48550/ARXIV.2207.11832 , eprinttype =. 2207.11832 , timestamp =

    work page doi:10.48550/arxiv.2207.11832 2022

  27. [27]

    47th Annual

    Manor Mendel and Assaf Naor , title =. 47th Annual. 2006 , url =. doi:10.1109/FOCS.2006.65 , timestamp =

    work page doi:10.1109/focs.2006.65 2006

  28. [28]

    Algorithmica , volume =

    Ely Porat and Liam Roditty , title =. Algorithmica , volume =. 2013 , url =. doi:10.1007/S00453-013-9825-9 , timestamp =

    work page doi:10.1007/s00453-013-9825-9 2013

  29. [29]

    Compact routing schemes , booktitle =

    Mikkel Thorup and Uri Zwick , editor =. Compact routing schemes , booktitle =. 2001 , url =. doi:10.1145/378580.378581 , timestamp =

    work page doi:10.1145/378580.378581 2001

  30. [30]

    Mikkel Thorup and Uri Zwick , title =. J. 2005 , url =. doi:10.1145/1044731.1044732 , timestamp =

    work page doi:10.1145/1044731.1044732 2005

  31. [31]

    Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation , booktitle =

    Alina Harbuzova and Ce Jin and Virginia Vassilevska Williams and Zixuan Xu , editor =. Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.166 , timestamp =

    work page doi:10.1137/1.9781611977912.166 2024

  32. [32]

    Faster Approximate Distance Queries and Compact Routing in Sparse Graphs

    Rachit Agarwal and Brighten Godfrey and Sariel Har. Faster Approximate Distance Queries and Compact Routing in Sparse Graphs , journal =. 2012 , url =. 1201.2703 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  33. [33]

    Distance Oracles for Stretch Less Than 2 , booktitle =

    Rachit Agarwal and Philip Brighten Godfrey , editor =. Distance Oracles for Stretch Less Than 2 , booktitle =. 2013 , url =. doi:10.1137/1.9781611973105.38 , timestamp =

    work page doi:10.1137/1.9781611973105.38 2013

  34. [34]

    The Space-Stretch-Time Tradeoff in Distance Oracles , booktitle =

    Rachit Agarwal , editor =. The Space-Stretch-Time Tradeoff in Distance Oracles , booktitle =. 2014 , url =. doi:10.1007/978-3-662-44777-2\_5 , timestamp =

    work page doi:10.1007/978-3-662-44777-2 2014

  35. [35]

    Distance Oracles beyond the Thorup-Zwick Bound , journal =

    Mihai P. Distance Oracles beyond the Thorup-Zwick Bound , journal =. 2014 , url =. doi:10.1137/11084128X , timestamp =

    work page doi:10.1137/11084128x 2014

  36. [36]

    Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs , journal =

    Davide Bil. Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs , journal =. 2023 , url =. doi:10.48550/ARXIV.2307.11677 , eprinttype =. 2307.11677 , timestamp =

    work page doi:10.48550/arxiv.2307.11677 2023

  37. [37]

    A New Infinity of Distance Oracles for Sparse Graphs , booktitle =

    Mihai P. A New Infinity of Distance Oracles for Sparse Graphs , booktitle =. 2012 , url =. doi:10.1109/FOCS.2012.44 , timestamp =

    work page doi:10.1109/focs.2012.44 2012

  38. [38]

    Proceedings of the Seventeenth Annual

    Mikkel Thorup and Uri Zwick , title =. Proceedings of the Seventeenth Annual. 2006 , url =

    2006

  39. [39]

    2010 , url =

    Surender Baswana and Telikepalli Kavitha and Kurt Mehlhorn and Seth Pettie , title =. 2010 , url =. doi:10.1145/1868237.1868242 , timestamp =

    work page doi:10.1145/1868237.1868242 2010

  40. [40]

    2021 , issue_date =

    Bodwin, Greg and Williams, Virginia Vassilevska , title =. 2021 , issue_date =. doi:10.1145/3490147 , journal =

    work page doi:10.1145/3490147 2021

  41. [41]

    Bypassing Erd

    Merav Parter , editor =. Bypassing Erd. Automata, Languages, and Programming - 41st International Colloquium,. 2014 , url =. doi:10.1007/978-3-662-43951-7\_49 , timestamp =

    work page doi:10.1007/978-3-662-43951-7 2014

  42. [42]

    New Additive Spanners , booktitle =

    Shiri Chechik , editor =. New Additive Spanners , booktitle =. 2013 , url =. doi:10.1137/1.9781611973105.36 , timestamp =

    work page doi:10.1137/1.9781611973105.36 2013

  43. [43]

    Amir Abboud and Greg Bodwin , title =. J. 2017 , url =. doi:10.1145/3088511 , timestamp =

    work page doi:10.1145/3088511 2017

  44. [44]

    2018 , url =

    Amir Abboud and Greg Bodwin and Seth Pettie , title =. 2018 , url =. doi:10.1137/16M1105815 , timestamp =

    work page doi:10.1137/16m1105815 2018

  45. [45]

    2004 , url =

    Michael Elkin and David Peleg , title =. 2004 , url =. doi:10.1137/S0097539701393384 , timestamp =

    work page doi:10.1137/s0097539701393384 2004

  46. [46]

    On Approximate Distance Labels and Routing Schemes with Affine Stretch , booktitle =

    Ittai Abraham and Cyril Gavoille , editor =. On Approximate Distance Labels and Routing Schemes with Affine Stretch , booktitle =. 2011 , url =. doi:10.1007/978-3-642-24100-0\_39 , timestamp =

    work page doi:10.1007/978-3-642-24100-0 2011

  47. [47]

    Approximate distance oracles with constant query time , booktitle =

    Shiri Chechik , editor =. Approximate distance oracles with constant query time , booktitle =. 2014 , url =. doi:10.1145/2591796.2591801 , timestamp =

    work page doi:10.1145/2591796.2591801 2014

  48. [48]

    Approximate Distance Oracles with Improved Bounds , booktitle =

    Shiri Chechik , editor =. Approximate Distance Oracles with Improved Bounds , booktitle =. 2015 , url =. doi:10.1145/2746539.2746562 , timestamp =

    work page doi:10.1145/2746539.2746562 2015

  49. [49]

    2010 , url =

    Surender Baswana and Telikepalli Kavitha , title =. 2010 , url =. doi:10.1137/080737174 , timestamp =

    work page doi:10.1137/080737174 2010

  50. [50]

    Approximate distance oracles with improved preprocessing time , booktitle =

    Christian Wulff. Approximate distance oracles with improved preprocessing time , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.18 , timestamp =

    work page doi:10.1137/1.9781611973099.18 2012

  51. [51]

    Space-efficient path-reporting approximate distance oracles , journal =

    Michael Elkin and Ofer Neiman and Christian Wulff. Space-efficient path-reporting approximate distance oracles , journal =. 2016 , url =. doi:10.1016/J.TCS.2016.07.038 , timestamp =

    work page doi:10.1016/j.tcs.2016.07.038 2016

  52. [52]

    2016 , url =

    Michael Elkin and Seth Pettie , title =. 2016 , url =. doi:10.1145/2888397 , timestamp =

    work page doi:10.1145/2888397 2016

  53. [53]

    Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size , booktitle =

    Shiri Chechik and Tianyi Zhang , editor =. Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size , booktitle =. 2024 , url =. doi:10.4230/LIPICS.ICALP.2024.42 , timestamp =

    work page doi:10.4230/lipics.icalp.2024.42 2024

  54. [54]

    Michael Elkin and Idan Shabat , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00141 , timestamp =

    work page doi:10.1109/focs57990.2023.00141 2023

  55. [55]

    2000 , url =

    Dorit Dor and Shay Halperin and Uri Zwick , title =. 2000 , url =. doi:10.1137/S0097539797327908 , timestamp =

    work page doi:10.1137/s0097539797327908 2000

  56. [56]

    Uri Zwick , title =. J. 2002 , url =. doi:10.1145/567112.567114 , timestamp =

    work page doi:10.1145/567112.567114 2002

  57. [57]

    Surender Baswana and Vishrut Goyal and Sandeep Sen , title =. Theor. Comput. Sci. , volume =. 2009 , url =. doi:10.1016/J.TCS.2008.10.018 , timestamp =

    work page doi:10.1016/j.tcs.2008.10.018 2009

  58. [58]

    2006 , url =

    Surender Baswana and Sandeep Sen , title =. 2006 , url =. doi:10.1145/1198513.1198518 , timestamp =

    work page doi:10.1145/1198513.1198518 2006

  59. [59]

    47th Annual

    Surender Baswana and Telikepalli Kavitha , title =. 47th Annual. 2006 , url =. doi:10.1109/FOCS.2006.29 , timestamp =

    work page doi:10.1109/focs.2006.29 2006

  60. [60]

    Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error , booktitle =

    Surender Baswana and Akshay Gaur and Sandeep Sen and Jayant Upadhyay , editor =. Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error , booktitle =. 2008 , url =. doi:10.1007/978-3-540-70575-8\_50 , timestamp =

    work page doi:10.1007/978-3-540-70575-8 2008

  61. [61]

    Approximate Distance Oracles with Improved Query Time , booktitle =

    Christian Wulff. Approximate Distance Oracles with Improved Query Time , booktitle =. 2013 , url =. doi:10.1137/1.9781611973105.39 , timestamp =

    work page doi:10.1137/1.9781611973105.39 2013

  62. [62]

    Deterministic Constructions of Approximate Distance Oracles and Spanners , booktitle =

    Liam Roditty and Mikkel Thorup and Uri Zwick , editor =. Deterministic Constructions of Approximate Distance Oracles and Spanners , booktitle =. 2005 , url =. doi:10.1007/11523468\_22 , timestamp =

    work page doi:10.1007/11523468 2005

  63. [63]

    Approximate distance queries and compact routing in sparse graphs , booktitle =

    Rachit Agarwal and Philip Brighten Godfrey and Sariel Har. Approximate distance queries and compact routing in sparse graphs , booktitle =. 2011 , url =. doi:10.1109/INFCOM.2011.5934973 , timestamp =

    work page doi:10.1109/infcom.2011.5934973 2011

  64. [64]

    Encyclopedia of Algorithms , pages =

    Liam Roditty , title =. Encyclopedia of Algorithms , pages =. 2016 , url =. doi:10.1007/978-1-4939-2864-4\_571 , timestamp =

    work page doi:10.1007/978-1-4939-2864-4 2016

  65. [65]

    Approximate Distance Oracle with Constant Query Time

    Shiri Chechik , title =. CoRR , volume =. 2013 , url =. 1305.3314 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  66. [66]

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

    Shiri Chechik and Tianyi Zhang , editor =. Nearly 2-Approximate Distance Oracles in Subquadratic Time , booktitle =. 2022 , url =. doi:10.1137/1.9781611977073.26 , timestamp =

    work page doi:10.1137/1.9781611977073.26 2022

  67. [67]

    Compact routing schemes with improved stretch , booktitle =

    Shiri Chechik , editor =. Compact routing schemes with improved stretch , booktitle =. 2013 , url =. doi:10.1145/2484239.2484268 , timestamp =

    work page doi:10.1145/2484239.2484268 2013

  68. [68]

    New Routing Techniques and their Applications , booktitle =

    Liam Roditty and Roei Tov , editor =. New Routing Techniques and their Applications , booktitle =. 2015 , url =. doi:10.1145/2767386.2767409 , timestamp =

    work page doi:10.1145/2767386.2767409 2015

  69. [69]

    2008 , url =

    Ittai Abraham and Cyril Gavoille and Dahlia Malkhi and Noam Nisan and Mikkel Thorup , title =. 2008 , url =. doi:10.1145/1367064.1367077 , timestamp =

    work page doi:10.1145/1367064.1367077 2008

  70. [70]

    Lenore Cowen , title =. J. Algorithms , volume =. 2001 , url =. doi:10.1006/JAGM.2000.1134 , timestamp =

    work page doi:10.1006/jagm.2000.1134 2001

  71. [71]

    Wagner , editor =

    Lenore Cowen and Christopher G. Wagner , editor =. Compact Roundtrip Routing for Digraphs , booktitle =. 1999 , url =

    1999

  72. [72]

    Compact Routing Tables for Graphs of Bounded Genus , booktitle =

    Cyril Gavoille and Nicolas Hanusse , editor =. Compact Routing Tables for Graphs of Bounded Genus , booktitle =. 1999 , url =. doi:10.1007/3-540-48523-6\_32 , timestamp =

    work page doi:10.1007/3-540-48523-6 1999

  73. [73]

    Algorithmica , volume =

    Lata Narayanan and Jaroslav Opatrny , title =. Algorithmica , volume =. 1999 , url =. doi:10.1007/PL00009251 , timestamp =

    work page doi:10.1007/pl00009251 1999

  74. [74]

    Improved Compact Routing Scheme for Chordal Graphs , booktitle =

    Yon Dourisboure and Cyril Gavoille , editor =. Improved Compact Routing Scheme for Chordal Graphs , booktitle =. 2002 , url =. doi:10.1007/3-540-36108-1\_17 , timestamp =

    work page doi:10.1007/3-540-36108-1 2002

  75. [75]

    Compact routing for average-case networks , booktitle =

    Kazuo Iwama and Masaki Okita , editor =. Compact routing for average-case networks , booktitle =. 2002 , url =. doi:10.1145/571825.571868 , timestamp =

    work page doi:10.1145/571825.571868 2002

  76. [76]

    Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees , booktitle =

    Hsueh. Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees , booktitle =. 2002 , url =. doi:10.1007/3-540-45655-4\_8 , timestamp =

    work page doi:10.1007/3-540-45655-4 2002

  77. [77]

    Compact Routing for Flat Networks , booktitle =

    Kazuo Iwama and Masaki Okita , editor =. Compact Routing for Flat Networks , booktitle =. 2003 , url =. doi:10.1007/978-3-540-39989-6\_14 , timestamp =

    work page doi:10.1007/978-3-540-39989-6 2003

  78. [78]

    Tiziana Calamoneri and Miriam Di Ianni , title =. J. Parallel Distributed Comput. , volume =. 2003 , url =. doi:10.1016/S0743-7315(03)00110-2 , timestamp =

    work page doi:10.1016/s0743-7315(03)00110-2 2003

  79. [79]

    Compact routing on euclidian metrics , booktitle =

    Ittai Abraham and Dahlia Malkhi , editor =. Compact routing on euclidian metrics , booktitle =. 2004 , url =. doi:10.1145/1011767.1011789 , timestamp =

    work page doi:10.1145/1011767.1011789 2004

  80. [80]

    Dragan and Irina Lomonosov , editor =

    Feodor F. Dragan and Irina Lomonosov , editor =. On Compact and Efficient Routing in Certain Graph Classes , booktitle =. 2004 , url =. doi:10.1007/978-3-540-30551-4\_36 , timestamp =

    work page doi:10.1007/978-3-540-30551-4 2004

Showing first 80 references.