pith. sign in

arxiv: 2606.31560 · v1 · pith:W3DDNLRGnew · submitted 2026-06-30 · 💻 cs.DS

Directed Low Diameter Decomposition for Structured Digraphs

Shinwoo An , Arnold Filtser This is my paper

Pith reviewed 2026-07-01 03:06 UTC · model grok-4.3

classification 💻 cs.DS
keywords directed graphslow diameter decompositionpathwidthtreewidthsparsest cutintegrality gapquasipartition
0
0 comments X

The pith

Directed graphs with pathwidth pw admit low-diameter decompositions with diameter linear in pw.

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

The paper establishes that any directed graph of pathwidth pw has an (O(pw), Δ)-LDD. This improves an earlier construction whose diameter depended exponentially on pw. The same refined quasipartition analysis also shows that the integrality gap of the directed non-bipartite sparsest-cut LP is O(tw log n) on any n-vertex graph of treewidth tw. These bounds matter because LDDs and sparsest-cut approximations are used as subroutines in many graph algorithms; linear or near-linear dependence on the width parameter therefore yields faster procedures precisely on the graphs that admit small width. The results are obtained by tightening the analysis of an existing quasipartition method rather than by inventing an entirely new construction.

Core claim

Any directed graph with pathwidth pw admits an (O(pw), Δ)-LDD. The integrality gap of the Directed Non-Bipartite Sparsest-Cut LP relaxation on an n-vertex graph with treewidth tw is O(tw log n). Both statements follow from a refined analysis of the quasipartition construction that works on bounded-treewidth and bounded-pathwidth digraphs.

What carries the argument

The refined quasipartition construction that produces both the linear-in-pw LDD and the O(tw log n) integrality gap.

If this is right

  • Every directed graph of pathwidth pw has an (O(pw), Δ)-LDD.
  • The directed non-bipartite sparsest-cut LP has integrality gap O(tw log n) on all treewidth-tw graphs.
  • The previous exponential dependence on pw for LDDs is replaced by linear dependence.
  • The previous O(tw log² n) integrality-gap bound is tightened by one logarithmic factor.

Where Pith is reading between the lines

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

  • The same refinement technique may produce improved LDDs or cut approximations for other width measures such as branchwidth.
  • Faster approximation algorithms for directed cut and clustering problems become possible on the subclass of low-pathwidth or low-treewidth digraphs.
  • The linear LDD bound may combine with dynamic-programming methods that already run in 2^O(pw) n time to give end-to-end polynomial dependence on pw for some problems.

Load-bearing premise

The existing quasipartition construction admits a tighter analysis that removes the extra logarithmic factor from the gap and yields linear dependence on pathwidth.

What would settle it

An explicit directed graph of pathwidth pw on which every LDD requires diameter ω(pw), or an n-vertex treewidth-tw digraph whose directed non-bipartite sparsest-cut LP gap is ω(tw log n).

Figures

Figures reproduced from arXiv: 2606.31560 by Arnold Filtser, Shinwoo An.

Figure 1
Figure 1. Figure 1: Counter-example of Lemma 1 for directed graphs. Consider a directed graph [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Due to the definition of δ ∗ (·), every SCC of H \δ ∗ (B1) is either contained in B1 or disjoint from B1. The same holds symmetrically for B2. Therefore, every SCC of H \ (δ ∗ (B1) ∪ δ ∗ ′ (B2)) is fully contained in one of the regions of the Venn diagram. This proves both items of Lemma 3 for the special case of C = G. See Section 4 for the general case. C, denoted as P[C], as the u-v subpath of P. Note t… view at source ↗
Figure 3
Figure 3. Figure 3: (a) Illustration of the first stage. The gray region denotes two balls B + G (u, R) and B − G (v, R) where R is sampled from [ 1 2 τ, 2 3 τ ] with τ = dG(u, v). For an SCC C ′ (yellow region) contained in B1 = B + G (u, R) and x, y ∈ P ∩ C ′ , we have that dG(x, y) ≤ dG(u, y) ≤ 2 3 τ , since P is a shortest path in G. (b) Illustration of the second stage. The blue region denotes B − G (u, R), and P ′ repre… view at source ↗
Figure 4
Figure 4. Figure 4: (a) Illustration of the graph partition from the first two stages. In the first stage, an out-ball B + G (w, ∆) (light gray region) containing u, v is computed. In the second stage, an out-ball B + G (v, 8∆) (dark gray region) containing u is computed. (b) At the start of the third stage, an SCC (blue region) might have a large diameter, as no upper bounds for dG(x, u) and dG(y, u) are assumed. In the thir… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the critical path and critical sequence of [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
read the original abstract

Low diameter decompositions, or LDDs for short, are a fundamental primitive in the design of efficient graph algorithms. Roughly speaking, an LDD is a distribution over partitions of the vertices into bounded-diameter clusters such that nearby vertices are likely to be clustered together. Recently, there has been growing interest in lifting the notion of LDDs into \emph{directed graphs}. In particular, there are two natural directed analogues. The first is a directed LDD, where after removing a random subset of edges, every strongly connected component has a small diameter. The second is a quasipartition, which imposes the stronger requirement that whenever one vertex can still reach another after the edge removal, the two vertices must be close in the original directed metric. Every quasipartition yields an LDD, but the converse does not necessarily hold. In this work, we initiate the systematic study of LDDs in structured directed graphs. As our first main result, we show that any directed graph with pathwidth $\mathsf{pw}$ admits an $(O(\mathsf{pw}), \Delta)$-LDD. This improves upon the previous best-known $(2^{O(\mathsf{pw}^2)}, \Delta)$-LDD construction, which was implicitly derived from the quasipartition result of Salmasi, Sidiropoulos, and Sridhar [SODA'19]. As our second result, we show that the integrality gap of the Directed Non-Bipartite Sparsest-Cut LP relaxation on an $n$-vertex graph with treewidth $\mathsf{tw}$ is $O(\mathsf{tw} \log n)$. This improves upon the $O(\mathsf{tw}\log^2 n)$ bound of M\'emoli, Sidiropoulos, and Sridhar [ICALP'16, Algorithmica'18]. We obtain this result through the refined analysis of the quasipartition construction of M\'emoli et al. for bounded treewidth 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 paper claims two main results on directed low-diameter decompositions (LDDs) and related quasipartitions in structured digraphs. For any directed graph with pathwidth pw it constructs an (O(pw), Δ)-LDD, improving the prior (2^{O(pw²)}, Δ) bound implicitly obtained from Salmasi et al. (SODA'19). For the Directed Non-Bipartite Sparsest-Cut LP on n-vertex graphs of treewidth tw it proves an integrality gap of O(tw log n), improving the O(tw log² n) bound of Mémoli et al. (ICALP'16, Algorithmica'18). Both improvements are obtained by a refined analysis of the existing quasipartition construction of Mémoli, Sidiropoulos and Sridhar rather than a new construction.

Significance. If the refined analysis is correct, the results tighten the dependence on pathwidth and treewidth for two fundamental primitives, removing an exponential factor in the LDD bound and a logarithmic factor in the integrality gap. Such improvements are useful for approximation algorithms and exact algorithms on low-treewidth/pathwidth digraphs. The paper explicitly builds on and credits the prior quasipartition construction, which is a positive feature when the improvement arises from careful re-analysis.

minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly state whether the O(pw) LDD bound is with respect to the directed metric or the underlying undirected metric, and whether Δ is the maximum out-degree or total degree; this notation is used without definition in the provided abstract.
  2. [Introduction / Technical sections] The claim that the new integrality gap follows from 'refined analysis' of the Mémoli et al. quasipartition should be accompanied, in §3 or the relevant technical section, by a short comparison table or paragraph highlighting exactly which step in the original analysis is tightened and by how much.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the improvements, and recommendation for minor revision. We appreciate the note that the work builds on and credits the prior quasipartition construction.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central results—an (O(pw), Δ)-LDD for pathwidth-pw digraphs and an O(tw log n) integrality gap for the directed sparsest-cut LP on treewidth-tw graphs—are obtained by refining the analysis of an existing quasipartition construction due to Mémoli, Sidiropoulos, and Sridhar (ICALP'16/Algorithmica'18). This prior construction is external to the present authors and is not derived from or fitted to the target bounds; the improvement consists of a tighter analysis that removes a log factor. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The claims rest on independent analytic refinement rather than reduction to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard definitions of pathwidth, treewidth, and quasipartitions together with the existence of prior constructions; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math Standard definitions and metric properties of pathwidth and treewidth for directed graphs.
    The statements are parameterized by these graph-width measures.
  • domain assumption The quasipartition construction of Mémoli et al. exists and admits further analysis.
    The paper obtains its bounds by refining that prior construction.

pith-pipeline@v0.9.1-grok · 5897 in / 1365 out tokens · 59392 ms · 2026-07-01T03:06:11.748438+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

294 extracted references · 178 canonical work pages · 1 internal anchor

  1. [1]

    I, Discrete Math

    Noga Alon , title =. I, Discrete Math. , volume =. 2003 , pages =

    2003

  2. [2]

    Assouad , title =

    P. Assouad , title =. Bull. Soc. Math. France , volume =. 1983 , pages =

    1983

  3. [3]

    Awerbuch, Baruch , title =. J. ACM , issue_date =. 1985 , issn =. doi:10.1145/4221.4227 , acmid =

    work page doi:10.1145/4221.4227 1985

  4. [4]

    2006 , url =

    Noga Alon and Baruch Awerbuch and Yossi Azar and Niv Buchbinder and Joseph Naor , title =. 2006 , url =. doi:10.1145/1198513.1198522 , timestamp =

    work page doi:10.1145/1198513.1198522 2006

  5. [5]

    Proceedings of the 48th Annual

    Amir Abboud and Greg Bodwin , title =. Proceedings of the 48th Annual. 2016 , crossref =. doi:10.1145/2897518.2897555 , timestamp =

    work page doi:10.1145/2897518.2897555 2016

  6. [6]

    Graph Theory and Related Topics , Year =

    A Conjecture on Planar Graphs , Author =. Graph Theory and Related Topics , Year =

  7. [7]

    34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993 , pages =

    Baruch Awerbuch and Bonnie Berger and Lenore Cowen and David Peleg , title =. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993 , pages =. 1993 , crossref =. doi:10.1109/SFCS.1993.366823 , timestamp =

    work page doi:10.1109/sfcs.1993.366823 1993

  8. [8]

    Region-Fault Tolerant Geometric Spanners , Author =. Discret. Comput. Geom. , Year =. doi:10.1007/s00454-009-9137-7 , Timestamp =

    work page doi:10.1007/s00454-009-9137-7

  9. [9]

    1999 , url =

    Richa Agarwala and Vineet Bafna and Martin Farach and Mike Paterson and Mikkel Thorup , title =. 1999 , url =. doi:10.1137/S0097539795296334 , timestamp =

    work page doi:10.1137/s0097539795296334 1999

  10. [10]

    Improved Routing Strategies with Succinct Tables , journal =

    Baruch Awerbuch and Amotz Bar. Improved Routing Strategies with Succinct Tables , journal =. 1990 , url =. doi:10.1016/0196-6774(90)90017-9 , timestamp =

    work page doi:10.1016/0196-6774(90)90017-9 1990

  11. [11]

    2007 , note =

    Ittai Abraham and Yair Bartal and Ofer Neiman , title =. 2007 , note =

    2007

  12. [12]

    Ittai Abraham and Yair Bartal and Ofer Neiman , title = "On Embedding of Finite Metric Spaces into. 2005

    2005

  13. [13]

    STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , year =

    Ittai Abraham and Yair Bartal and Ofer Neiman , title =. STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , year =. doi:http://doi.acm.org/10.1145/1132516.1132557 , publisher =

    work page doi:10.1145/1132516.1132557

  14. [14]

    Ittai Abraham and Yair Bartal and Ofer Neiman , title=. 2006

    2006

  15. [15]

    Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms , series =

    Abraham, Ittai and Bartal, Yair and Neiman, Ofer , title =. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms , series =. 2007 , isbn =

    2007

  16. [16]

    Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , series =

    Abraham, Ittai and Bartal, Yair and Neiman, Ofer , title =. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , series =. 2007 , isbn =. doi:10.1145/1250790.1250883 , acmid =

    work page doi:10.1145/1250790.1250883 2007

  17. [17]

    Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , series =

    Abraham, Ittai and Bartal, Yair and Neiman, Ofer , title =. Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , series =. 2008 , location =

    2008

  18. [18]

    FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , year =

    Abraham, Ittai and Bartal, Yair and Neiman, Ofer , title =. FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , year =. doi:http://dx.doi.org/10.1109/FOCS.2008.62 , isbn =

    work page doi:10.1109/focs.2008.62 2008

  19. [19]

    SODA '09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms , year =

    Abraham, Ittai and Bartal, Yair and Neiman, Ofer , title =. SODA '09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms , year =

  20. [20]

    Advances in metric embedding theory , journal =

    Ittai Abraham and Yair Bartal and Ofer Neiman , keywords =. Advances in metric embedding theory , journal =. 2011 , issn =. doi:https://doi.org/10.1016/j.aim.2011.08.003 , url =

    work page doi:10.1016/j.aim.2011.08.003 2011

  21. [21]

    Baratz and David Peleg , title =

    Baruch Awerbuch and Alan E. Baratz and David Peleg , title =. Proceedings of the Ninth Annual. 1990 , crossref =. doi:10.1145/93385.93417 , timestamp =

    work page doi:10.1145/93385.93417 1990

  22. [22]

    Technical Report CS92-22, Weizmann Institute , Year =

    Efficient Broadcast and Light-Weight Spanners , Author =. Technical Report CS92-22, Weizmann Institute , Year =

  23. [23]

    Awerbuch and A

    B. Awerbuch and A. Baratz and D. Peleg , title =. 1992 , number =

    1992

  24. [25]

    Proceedings of the 2025 Annual

    Yufan Huang and Peter Jin and Kent Quanrud , title =. Proceedings of the 2025 Annual

    2025

  25. [26]

    Kobourov and Richard Spence , Journal =

    Abu Reyan Ahmed and Greg Bodwin and Faryad Darabi Sahneh and Keaton Hamm and Mohammad Javad Latifi Jebelli and Stephen G. Kobourov and Richard Spence , Journal =. Graph spanners:. 2020 , Pages =. doi:10.1016/j.cosrev.2020.100253 , Timestamp =

    work page doi:10.1016/j.cosrev.2020.100253 2020

  26. [27]

    2009 , url =

    Nir Ailon and Bernard Chazelle , title =. 2009 , url =. doi:10.1137/060673096 , timestamp =

    work page doi:10.1137/060673096 2009

  27. [28]

    Proceedings of the Twenty-Ninth Annual

    Ramsey Spanning Trees and their Applications , Author =. Proceedings of the Twenty-Ninth Annual. 2018 , Note =. doi:10.1137/1.9781611975031.108 , Timestamp =

    work page doi:10.1137/1.9781611975031.108 2018

  28. [29]

    2020 , Note =

    Ramsey Spanning Trees and Their Applications , Author =. 2020 , Note =. doi:10.1145/3371039 , Timestamp =

    work page doi:10.1145/3371039 2020

  29. [30]

    Approximate Nearest Neighbor Search in Metrics of Planar Graphs , booktitle =

    Ittai Abraham and Shiri Chechik and Robert Krauthgamer and Udi Wieder , editor =. Approximate Nearest Neighbor Search in Metrics of Planar Graphs , booktitle =. 2015 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.20 , timestamp =

    work page doi:10.4230/lipics.approx-random.2015.20 2015

  30. [31]

    Adamaszek and A

    A. Adamaszek and A. Czumaj and A. Lingas , Booktitle =. 2009 , Pages =. doi:10.1007/978-3-642-10631-6_100 , Owner =

    work page doi:10.1007/978-3-642-10631-6_100 2009

  31. [32]

    Generating Sparse Spanners for Weighted Graphs , booktitle =

    Ingo Alth. Generating Sparse Spanners for Weighted Graphs , booktitle =. 1990 , pages =

    1990

  32. [33]

    On Sparse Spanners of Weighted Graphs , journal =

    Ingo Alth. On Sparse Spanners of Weighted Graphs , journal =. 1993 , url =. doi:10.1007/BF02189308 , timestamp =

    work page doi:10.1007/bf02189308 1993

  33. [34]

    27th Annual European Symposium on Algorithms,

    Constructing Light Spanners Deterministically in Near-Linear Time , Author =. 27th Annual European Symposium on Algorithms,. 2019 , Pages =. doi:10.4230/LIPIcs.ESA.2019.4 , Timestamp =

    work page doi:10.4230/lipics.esa.2019.4 2019

  34. [35]

    Constructing light spanners deterministically in near-linear time , journal =

    Stephen Alstrup and S. Constructing light spanners deterministically in near-linear time , journal =. 2022 , url =. doi:10.1016/j.tcs.2022.01.021 , timestamp =

    work page doi:10.1016/j.tcs.2022.01.021 2022

  35. [36]

    Journal of Experimental Algorithmics (JEA) , Year =

    Partitioning planar graphs with costs and weights , Author =. Journal of Experimental Algorithmics (JEA) , Year =

  36. [37]

    Mount and Jeffrey S

    Sunil Arya and Gautam Das and David M. Mount and Jeffrey S. Salowe and Michiel H. M. Smid , editor =. Euclidean spanners: short, thin, and lanky , booktitle =. 1995 , url =. doi:10.1145/225058.225191 , timestamp =

    work page doi:10.1145/225058.225191 1995

  37. [38]

    CoRR , keywords =

    Andersen, Reid and Feige, Uriel , title =. CoRR , keywords =. 2009 , added-at =

    2009

  38. [39]

    Proceedings of the 50th Annual

    Metric embedding via shortest path decompositions , Author =. Proceedings of the 50th Annual. 2018 , Pages =. doi:10.1145/3188745.3188808 , Timestamp =

    work page doi:10.1145/3188745.3188808 2018

  39. [40]

    2022 , url =

    Ittai Abraham and Arnold Filtser and Anupam Gupta and Ofer Neiman , title =. 2022 , url =. doi:10.1137/19m1296021 , timestamp =

    work page doi:10.1137/19m1296021 2022

  40. [41]

    Approximating

    Ernst Althaus and Stefan Funke and Sariel Har. Approximating. Oper. Res. Lett. , volume =. 2005 , url =. doi:10.1016/j.orl.2004.05.005 , timestamp =

    work page doi:10.1016/j.orl.2004.05.005 2005

  41. [42]

    Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing , Year =

    Object Location Using Path Separators , Author =. Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing , Year =. doi:10.1145/1146381.1146411 , Owner =

    work page doi:10.1145/1146381.1146411

  42. [43]

    and Malkhi, Dahlia , TITLE =

    Abraham, Ittai and Gavoille, Cyril and Goldberg, Andrew V. and Malkhi, Dahlia , TITLE =. 26^

  43. [44]

    Abraham and C

    I. Abraham and C. Gavoille and A. Gupta and O. Neiman and K. Talwar , Booktitle =. Cops, Robbers, and Threatening Skeletons:. 2014 , Pages =. doi:10.1145/2591796.2591849 , Owner =

    work page doi:10.1145/2591796.2591849 2014

  44. [45]

    2019 , Note =

    Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs , Author =. 2019 , Note =. doi:10.1137/17M1112406 , Timestamp =

    work page doi:10.1137/17m1112406 2019

  45. [46]

    Distance Labeling Schemes for Trees , booktitle =

    Stephen Alstrup and Inge Li G. Distance Labeling Schemes for Trees , booktitle =. 2016 , crossref =. doi:10.4230/LIPIcs.ICALP.2016.132 , timestamp =

    work page doi:10.4230/lipics.icalp.2016.132 2016

  46. [47]

    Karger and Philip N

    Sanjeev Arora and Michelangelo Grigni and David R. Karger and Philip N. Klein and Andrzej Woloszyn , Booktitle =. A Polynomial-Time Approximation Scheme for Weighted Planar Graph. 1998 , Pages =

    1998

  47. [48]

    SIAM Journal on Computing , Year =

    Local Search Heuristics for k -Median and Facility Location Problems , Author =. SIAM Journal on Computing , Year =. doi:10.1137/S0097539702416402 , Owner =

    work page doi:10.1137/s0097539702416402

  48. [49]

    Theory Comput

    Stephen Alstrup and Cyril Gavoille and Haim Kaplan and Theis Rauhe , title =. Theory Comput. Syst. , volume =. 2004 , url =. doi:10.1007/s00224-004-1155-5 , timestamp =

    work page doi:10.1007/s00224-004-1155-5 2004

  49. [50]

    Routing with Improved Communication-Space Trade-Off , booktitle =

    Ittai Abraham and Cyril Gavoille and Dahlia Malkhi , editor =. Routing with Improved Communication-Space Trade-Off , booktitle =. 2004 , url =. doi:10.1007/978-3-540-30186-8\_22 , timestamp =

    work page doi:10.1007/978-3-540-30186-8 2004

  50. [51]

    Compact Routing for Graphs Excluding a Fixed Minor , booktitle =

    Ittai Abraham and Cyril Gavoille and Dahlia Malkhi , editor =. Compact Routing for Graphs Excluding a Fixed Minor , booktitle =. 2005 , url =. doi:10.1007/11561927\_32 , timestamp =

    work page doi:10.1007/11561927 2005

  51. [52]

    On space-stretch trade-offs: lower bounds , booktitle =

    Ittai Abraham and Cyril Gavoille and Dahlia Malkhi , editor =. On space-stretch trade-offs: lower bounds , booktitle =. 2006 , url =. doi:10.1145/1148109.1148143 , timestamp =

    work page doi:10.1145/1148109.1148143 2006

  52. [53]

    Proceedings of the 31st

    Graph sketches: sparsification, spanners, and subgraphs , Author =. Proceedings of the 31st. 2012 , Pages =. doi:10.1145/2213556.2213560 , Timestamp =

    work page doi:10.1145/2213556.2213560 2012

  53. [54]

    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

  54. [55]

    Theory of Computing Systems , Year =

    Strong-Diameter Decompositions of Minor Free Graphs , Author =. Theory of Computing Systems , Year =. doi:10.1007/s00224-010-9283-6 , Owner =

    work page doi:10.1007/s00224-010-9283-6

  55. [56]

    Ahmed and G

    R. Ahmed and G. Bodwin and F. D. Sahneh and K. Hamm and M. J. L Jebelli and S. Kobourov and R. Spence , Journal =. Graph spanners:. 2019 , Note =

    2019

  56. [57]

    Theory Comput

    Sanjeev Arora and Elad Hazan and Satyen Kale , title =. Theory Comput. , volume =. 2012 , url =. doi:10.4086/toc.2012.v008a006 , timestamp =

    work page doi:10.4086/toc.2012.v008a006 2012

  57. [58]

    Graphs Comb

    The Moore Bound for Irregular Graphs , Author =. Graphs Comb. , Year =. doi:10.1007/s003730200002 , Timestamp =

    work page doi:10.1007/s003730200002

  58. [59]

    Near-optimal labeling schemes for nearest common ancestors , booktitle =

    Stephen Alstrup and Esben Bistrup Halvorsen and Kasper Green Larsen , editor =. Near-optimal labeling schemes for nearest common ancestors , booktitle =. 2014 , url =. doi:10.1137/1.9781611973402.72 , timestamp =

    work page doi:10.1137/1.9781611973402.72 2014

  59. [60]

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

    Assadi, Sepehr and Hoppenworth, Gary and Wein, Nicole , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =. 2025 , isbn =. doi:10.1145/3717823.3718298 , abstract =

    work page doi:10.1145/3717823.3718298 2025

  60. [61]

    Alexandr Andoni and Piotr Indyk , title =. Commun. 2008 , url =. doi:10.1145/1327452.1327494 , timestamp =

    work page doi:10.1145/1327452.1327494 2008

  61. [62]

    Razenshteyn , title =

    Alexandr Andoni and Piotr Indyk and Ilya P. Razenshteyn , title =. CoRR , volume =. 2018 , url =. 1806.09823 , timestamp =

    Pith/arXiv arXiv 2018

  62. [63]

    1994 , url =

    Baruch Awerbuch and Shay Kutten and David Peleg , title =. 1994 , url =. doi:10.1109/26.328973 , timestamp =

    work page doi:10.1109/26.328973 1994

  63. [64]

    Karp and David Peleg and Douglas B

    Noga Alon and Richard M. Karp and David Peleg and Douglas B. West , title =. 1995 , url =. doi:10.1137/S0097539792224474 , timestamp =

    work page doi:10.1137/s0097539792224474 1995

  64. [65]

    Klein and R

    Ajit Agrawal and Philip N. Klein and R. Ravi , title =. 1995 , url =. doi:10.1137/S0097539792236237 , timestamp =

    work page doi:10.1137/s0097539792236237 1995

  65. [66]

    Asano and N

    T. Asano and N. Katoh and H. Tamaki and T. Tokuyama , Booktitle =. Covering Points in the Plane by K -Tours:. 1997 , Pages =. doi:10.1145/258533.258602 , Owner =

    work page doi:10.1145/258533.258602 1997

  66. [67]

    Proceedings of the 30th Annual Symposium on Foundations of Computer Science , Year =

    Network Decomposition and Locality in Distributed Computation , Author =. Proceedings of the 30th Annual Symposium on Foundations of Computer Science , Year =. doi:10.1109/SFCS.1989.63504 , Owner =

    work page doi:10.1109/sfcs.1989.63504 1989

  67. [68]

    STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing , year=

    Euclidean Distortion and the Sparsest Cut , author=. STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing , year=

  68. [69]

    Lee and Assaf Naor , title =

    Sanjeev Arora and James R. Lee and Assaf Naor , title =. Discrete. 2007 , url =. doi:10.1007/s00454-007-9007-0 , timestamp =

    work page doi:10.1007/s00454-007-9007-0 2007

  69. [70]

    Arora and J

    S. Arora and J. R. Lee and A. Naor , title =. Journal of the American Mathematical Society 21 , year =

  70. [71]

    , TITLE =

    Alon, N. , TITLE =. Combinatorica , FJOURNAL =. 1986 , NUMBER =

    1986

  71. [72]

    Alspach , Journal =

    B. Alspach , Journal =. The wonderful. 2008 , Pages =

    2008

  72. [73]

    Mount and Michiel H

    Sunil Arya and David M. Mount and Michiel H. M. Smid , title =. 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994 , pages =. 1994 , crossref =. doi:10.1109/SFCS.1994.365722 , timestamp =

    work page doi:10.1109/sfcs.1994.365722 1994

  73. [74]

    Dynamic algorithms for geometric spanners of small diameter: Randomized solutions , Author =. Comput. Geom. , Year =

  74. [75]

    The Space Complexity of Approximating the Frequency Moments , Author =. J. Comput. Syst. Sci. , Year =. doi:10.1006/jcss.1997.1545 , Timestamp =

    work page doi:10.1006/jcss.1997.1545 1997

  75. [76]

    Journal of Graph Theory , Year =

    Large induced forests in sparse graphs , Author =. Journal of Graph Theory , Year =. doi:10.1002/jgt.1028 , Owner =

    work page doi:10.1002/jgt.1028

  76. [77]

    Proceedings of the 44th Symposium on Theory of Computing Conference,

    Ittai Abraham and Ofer Neiman , title =. Proceedings of the 44th Symposium on Theory of Computing Conference,. 2012 , crossref =. doi:10.1145/2213977.2214015 , timestamp =

    work page doi:10.1145/2213977.2214015 2012

  77. [78]

    2019 , Note =

    Using Petal-Decompositions to Build a Low Stretch Spanning Tree , Author =. 2019 , Note =. doi:10.1137/17M1115575 , Timestamp =

    work page doi:10.1137/17m1115575 2019

  78. [79]

    Thomas Andreae , title =. J. Comb. Theory, Ser. 1986 , url =. doi:10.1016/0095-8956(86)90026-2 , timestamp =

    work page doi:10.1016/0095-8956(86)90026-2 1986

  79. [80]

    2009 , school=

    Nearest neighbor search: the old, the new, and the impossible , author=. 2009 , school=

    2009

  80. [81]

    Nguyen and Aleksandar Nikolov and Ilya P

    Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya P. Razenshteyn and Erik Waingarten , editor =. Approximate near neighbors for general symmetric norms , booktitle =. 2017 , url =. doi:10.1145/3055399.3055418 , timestamp =

    work page doi:10.1145/3055399.3055418 2017

Showing first 80 references.