Pith. sign in

REVIEW 5 minor 159 references

Every Okamura–Seymour metric has a unique medial template whose arrangements give all minimum edge-count realizations, with lengths computable in polynomial time.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-12 06:23 UTC pith:NQ7OE2E5

load-bearing objection Clean combinatorial solution: OS metrics determine a unique minimum-crossing medial template whose arrangements are exactly the min-edge realizations.

arxiv 2607.02883 v1 pith:NQ7OE2E5 submitted 2026-07-03 cs.DS cs.CGmath.CO

Paths and Intersections: Minimum Realization of Okamura-Seymour Instances

Yu Chen , Pavlo Pylyavskyy , Zihan Tan This is my paper
classification cs.DS cs.CGmath.CO MSC 05C1205C8568R1090C35
keywords Okamura-Seymour instancesminimum realizationKalmanson metricsmedial graphsrepelling pairsshortest-path metricsY-Δ transformationsdisk-embedded graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

An Okamura–Seymour metric records shortest-path distances among terminals that sit on the boundary of a disk. The paper asks for the sparsest disk-embedded graphs that realize those distances exactly. It shows that the metric itself forces a single canonical matching of boundary points—the medial template—and that every minimum-edge realization is simply the primal graph of some arrangement of that template. The same template also supplies the exact minimum edge count. For any such graph the authors construct a good family of shortest paths and then recover nonnegative edge lengths that realize the metric. The argument treats the graph as a system of paths and their forced intersections, using repelling pairs as certificates that certain paths must stay vertex-disjoint.

Core claim

For any OS metric D the cut numbers b_{x,y} derived from maximum repelling sets determine a unique medial template Φ(D). The graph structures of all minimum realizations of D are exactly the primal graphs of arrangements of Φ(D); each has precisely cr(Φ(D)) edges, and nonnegative lengths realizing D can be computed efficiently on every such graph.

What carries the argument

The medial template Φ(D): the unique perfect matching on alternating boundary points whose crossing numbers equal the corrected repelling cut sizes b_{x,y}. Arrangements of this template produce all minimum primal graphs, because crossings of medial chords become edges and the cut inequalities of Theorem 5 become tight.

Load-bearing premise

The claim rests on the equivalence that a graph admits a good shortest-path structure if and only if no repelling set of pairs crosses any chain more times than the chain’s length.

What would settle it

Exhibit an OS metric D and a disk graph G that satisfies every chain inequality |M| ≤ |A| yet fails to admit any family of paths that are simultaneously vertex-disjoint on all repelling pairs and whose pairwise intersections are single subpaths; or produce two distinct templates both achieving the minimum crossing number for the same b_{x,y} numbers.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • All minimum OS realizations of a given metric share the same number of edges, equal to the crossing number of Φ(D).
  • The distinct embedded graphs realizing a metric with the fewest edges are related by Y–Δ moves that preserve the medial pairing.
  • Both the template and one concrete weighted realization can be recovered in polynomial time from the distance matrix alone.
  • Edge lengths realizing D on a fixed minimum graph need not be unique, even though the combinatorial structure is canonical.

Where Pith is reading between the lines

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

  • The same path-and-intersection viewpoint may yield minimum realizations for other planar or outerplanar metric families once suitable repelling certificates are defined.
  • Because the medial template is uniquely determined by local cut data, it supplies a compact certificate of structural complexity that could be used for metric compression or network tomography on disk-like topologies.
  • If the inductive construction of good paths can be derandomized or made fully combinatorial, the algorithm becomes a purely combinatorial reconstruction procedure with no numerical linear algebra.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper solves the minimum-edge realization problem for Okamura–Seymour metrics: given a Kalmanson metric D on a cyclically ordered terminal set T, recover all disk-embedded graphs with the fewest edges that realize D as shortest-path distances with the prescribed boundary order. The authors introduce repelling pairs (metric certificates of forced path separation), prove that an OS instance admits a D-good shortest-path structure if and only if every repelling set M and every chain A satisfy |M| ≤ |A| (Theorem 5), and show that the resulting cut numbers a_{x,y} (after endpoint correction to b_{x,y}) determine a unique medial template Φ(D) via circular inversion (Lemma 13). Minimum realizations are exactly the primal graphs of arrangements of Φ(D) (Lemma 16), each having cr(Φ(D)) edges; for any such graph, nonnegative edge lengths realizing D can be computed efficiently (Theorem 19). The development is paralleled with the inverse problem for electrical networks (Table 1).

Significance. The result gives a complete structural and algorithmic solution for minimum OS realizations: a canonical template is recovered from D alone, all minimal embedded graphs are identified as arrangements of that template, and realizing lengths are efficiently obtainable. The paths-and-intersections viewpoint, the characterization via repelling pairs and chains, and the exact parallel with critical electrical networks are of independent interest for metric graph theory and planar algorithms. The claims are constructive and the non-uniqueness of lengths is correctly exhibited (Appendix A). If the polynomial-time claims hold, the paper supplies a clean, usable compression of OS metrics.

minor comments (5)
  1. Theorem 1 and the opening of Section 4 assert that the template (hence all a_{x,y}/b_{x,y}) can be computed in polynomial time, yet no explicit procedure is given for evaluating the maximum size of a mutually repelling set of pairs that cross a given cut. While Observation 2 and the ordered-exchange arguments of Lemma 10 suggest a greedy or DP algorithm exists, a short paragraph or reference confirming poly-time computability would make the efficiency claim self-contained.
  2. Figure 1 caption refers to “path Π[i+1, j+1] (red)”; the surrounding text and construction use Π[i+1, j−1]. Correct the index.
  3. The concurrent preprint [CT26] is cited for Lemma 3 and for the uncrossing lemma used in Theorem 15. A one-sentence statement of the precise statements borrowed would help readers who do not yet have access to that manuscript.
  4. In the definition of chains (Definition 4) the length |A| counts only vertices; a parenthetical reminder that peripheral regions contribute zero would reduce the chance of off-by-one confusion when the endpoint correction for b_{x,y} is introduced.
  5. Table 1 is helpful; adding a one-line pointer in the caption to the precise theorems that justify each row of the “Distance realization” column would improve readability.

Circularity Check

2 steps flagged

Minor self-citations to concurrent work supply two auxiliary black-box lemmas; the template extraction from cut numbers and the chain-characterization of good structures are derived independently inside the paper.

specific steps
  1. self citation load bearing [Lemma 14 (Section 4.3) and its invocation in Theorem 15 / Lemma 16]
    "Lemma 14. If Φ ⪰ Φ′, then Φ → Φ′. The following lemma was proved in [CT26]."

    The claim that Φ(D) is the unique minimum-crossing feasible template (Theorem 15), and therefore that every minimum realization graph is an arrangement of exactly this template (Lemma 16), rests on the uncrossing implication imported from the concurrent self-citation. The implication itself is a parameter-free combinatorial fact about chord diagrams and does not presuppose the OS-metric results, so the dependence is mild rather than definitional.

  2. self citation load bearing [Lemma 3 (Section 2) and its use in Lemma 16 / Theorem 19]
    "Lemma 3. An OS instance (G, T) realizes a metric D on T iff it admits a good shortest path structure. Moreover, such an edge-length function in G, if it exists, can be found efficiently. The following lemma is proved in [CT26]."

    The direction “realizes ⇒ admits good SPS” is invoked to conclude that every realizing graph satisfies the chain lower bounds a_{x,y}, and the constructive length-finding algorithm is used to finish Theorem 19. Both pieces come from the concurrent self-citation. The paper independently proves the converse direction via its own inductive construction (Theorem 5), so the self-cite supplies only one half of the equivalence and the algorithmic recovery of lengths.

full rationale

The derivation begins from the metric D, defines repelling pairs and a_{x,y} by explicit maximization, corrects to b_{x,y}, and obtains the unique template Φ(D) by the linear inversion formula (4) together with the parity/uniqueness argument of Lemma 12 (all proved in-place). Theorem 5 constructs a good shortest-path structure from the chain inequalities by an inductive path-building argument that is self-contained. Arrangements of Φ(D) are then shown to satisfy those inequalities, hence to realize D once lengths are assigned, and to achieve the edge lower bound. The only external load-bearing ingredients are Lemma 3 (realizes ⇔ good SPS + length recovery) and Lemma 14 (uncrossing implication) from the authors’ concurrent paper [CT26]. Both are purely combinatorial statements independent of the target OS-metric claims; they function as black boxes and do not feed the definition of Φ(D) or the chain inequalities back into themselves. Consequently there is no self-definitional loop, no fitted-parameter-as-prediction, and no uniqueness theorem that merely renames the present result. The circularity score is therefore low.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 3 invented entities

The paper works entirely inside classical planar graph theory and metric geometry. No free parameters are fitted. The only non-standard objects are definitional (repelling pairs, chains, the derived template Φ(D)); they are introduced with explicit combinatorial definitions and used constructively. Background facts (Kalmanson characterization of OS metrics, medial-graph duality, Y-Δ distance preservation) are standard and cited.

axioms (3)
  • domain assumption A metric on a cyclically ordered terminal set is realizable by an OS instance if and only if it satisfies the Kalmanson four-point inequalities.
    Invoked from the first paragraph of Section 1 and used as the definition of an OS metric; classical result of Hurkens-Lovász-Schrijver-Tardos / Chepoi-Osajda.
  • domain assumption An OS instance realizes D if and only if it admits a D-good shortest-path structure (paths for every terminal pair that intersect in subpaths and are vertex-disjoint for repelling pairs).
    Lemma 3, cited from the authors' concurrent paper [CT26]; treated as a black-box equivalence throughout Sections 3-4.
  • standard math Y-Δ transformations preserve all terminal-to-terminal distances when the three new lengths are the standard non-negative combinations of the old ones.
    Recalled in Section 4.1; classical and used only to relate different arrangements of the same template.
invented entities (3)
  • repelling pairs / repelling sets no independent evidence
    purpose: Metric certificates that force shortest paths to be vertex-disjoint; supply the lower bounds a_{x,y} on chain lengths.
    Defined in Section 2 from the strict four-point inequality; the entire lower-bound theory rests on them. Independent evidence is internal (they are purely combinatorial).
  • medial template Φ(D) no independent evidence
    purpose: The unique perfect matching on the doubled boundary points whose cut distances equal the corrected repelling numbers b_{x,y}; its arrangements are exactly the minimum realizations.
    Constructed in Lemma 13 by circular inversion of the b-matrix; uniqueness and minimality of crossings are the main structural theorems. No external physical or experimental handle is claimed.
  • chains (vertex-region sequences from boundary to boundary) no independent evidence
    purpose: Discrete objects that count the number of primal vertices a set of paths must cross; convert repelling lower bounds into medial-chord lower bounds.
    Defined in Section 2; used as the combinatorial dual of medial cut distances. Purely definitional.

pith-pipeline@v1.1.0-grok45 · 20560 in / 2802 out tokens · 33562 ms · 2026-07-12T06:23:33.338493+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Paths and Intersections: Minimum Realization of Okamura-Seymour Instances." pith.science (2026). https://pith.science/paper/NQ7OE2E5

@misc{pith2026260702883,
  author       = {Pith},
  title        = {Pith review of: Paths and Intersections: Minimum Realization of Okamura-Seymour Instances},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NQ7OE2E5}},
  note         = {Machine review of arXiv:2607.02883}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We study the inverse problem for shortest-path metrics of Okamura-Seymour (OS) instances. Given an OS metric $D$ on a cyclically ordered terminal set $T$, the goal is to find minimum realizations of $D$, where minimum means having the fewest edges among all disk-embedded realizations with the prescribed terminal order. We show that $D$ determines a canonical medial graph template and every minimum realization is the primal graph of an arrangement of this template. Consequently, the underlying embedded graphs of minimum realizations of $D$ can be recovered, and for each such graph one can efficiently compute edge lengths realizing $D$. Our algorithm follows a recent approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Figures

Figures reproduced from arXiv: 2607.02883 by Pavlo Pylyavskyy, Yu Chen, Zihan Tan.

Figure 1
Figure 1. Figure 1: Path Π[i, j] in Case 1 (purple dashed line on the left): the other side of the the strip (light green area) supported by path Π[i+ 1, j + 1] (red), and the chain from vertex x built inductively (gray sequence on the right). gives a chain, and the singleton set M = {(i, j)} satisfies the conditions in the claim with this chain. Consider now a general pair i, j with j ≥ i + 2. We distinguish between the foll… view at source ↗
Figure 2
Figure 2. Figure 2: Path Π[i, j] (black), chain A (gray), path Π[j, i] (red) and chain A′ (pink). In the case where there is no bad pair, we construct a good shortest path structure as follows. If n is odd, then for every pair i, j of terminals, one of the two segments ∂[i, j], ∂[j, i] contains strictly fewer terminals than the other, say ∂[i, j], and we let Pi,j = Π[i, j]. If n is even, then we arbitrarily pick a non-termina… view at source ↗
Figure 3
Figure 3. Figure 3: Left: the primal graph. Terminals are shown in blue (the other reference points in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Minimum realizations of metric D: green edge weights are not unique. Consider a metric D on 8 points {t1, . . . , t8} defined as follows (indices modulo 8). • for each i, D(ti , ti+1) = 1, D(ti , ti+2) = 2, and D(ti , ti+3) = 3; and • D(t1, t5) = D(t3, t7) = 3, and D(t2, t6) = D(t4, t8) = 4. It is easy to verify that D is an OS metric in that all Kalmanson conditions are satisfied with respect to the natur… view at source ↗

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

159 extracted references · 18 linked inside Pith

  1. [1]

    arXiv preprint arXiv:2606.25827 , year=

    Paths and Intersections: Recognizing Outerplanar Metrics , author=. arXiv preprint arXiv:2606.25827 , year=

    Pith/arXiv arXiv

  2. [2]

    Louis and Yau, Stephen S

    Hakimi, S. Louis and Yau, Stephen S. , title =. Quarterly of Applied Mathematics , volume =. 1965 , doi =

    1965

  3. [3]

    Goldman, A. J. , title =. Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics , volume =. 1966 , doi =

    1966

  4. [4]

    On Optimal Realizations of Finite Metric Spaces by Graphs , journal =

    Alth. On Optimal Realizations of Finite Metric Spaces by Graphs , journal =. 1988 , doi =

    1988

  5. [5]

    SIAM Journal on Discrete Mathematics , volume =

    Winkler, Peter , title =. SIAM Journal on Discrete Mathematics , volume =. 1988 , doi =

    1988

  6. [6]

    Annual Symposium on Theoretical Aspects of Computer Science , pages=

    Representing graph metrics with fewest edges , author=. Annual Symposium on Theoretical Aspects of Computer Science , pages=. 2003 , organization=

    2003

  7. [7]

    arXiv preprint arXiv:2507.09620 , year=

    Paths and Intersections: Exact Emulators for Planar Graphs , author=. arXiv preprint arXiv:2507.09620 , year=

    Pith/arXiv arXiv

  8. [8]

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

    Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  9. [9]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Planar diameter via metric compression , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  10. [10]

    arXiv preprint arXiv:1807.01478 , year=

    Near-optimal distance emulator for planar graphs , author=. arXiv preprint arXiv:1807.01478 , year=

    Pith/arXiv arXiv

  11. [11]

    1972 , publisher=

    Multicommodity Maximum Flow in Planar Networks; the D-algorithm Approach , author=. 1972 , publisher=

    1972

  12. [12]

    Quarterly of applied mathematics , volume=

    The distance matrix of a graph and its tree realization , author=. Quarterly of applied mathematics , volume=

  13. [13]

    Discrete mathematics , volume=

    Trees related to realizations of distance matrices , author=. Discrete mathematics , volume=. 1998 , publisher=

    1998

  14. [14]

    Linear algebra and its applications , volume=

    Distance spectra of graphs: A survey , author=. Linear algebra and its applications , volume=. 2014 , publisher=

    2014

  15. [15]

    Algorithmica , volume=

    Composed degree-distance realizations of graphs , author=. Algorithmica , volume=. 2023 , publisher=

    2023

  16. [16]

    Discrete mathematics , volume=

    GRAPH REALIZATIONS , author=. Discrete mathematics , volume=

  17. [17]

    Linear Algebra and Its Applications , volume=

    Submatrices of non-tree-realizable distance matrices , author=. Linear Algebra and Its Applications , volume=. 1982 , publisher=

    1982

  18. [18]

    SIAM Journal on Discrete Mathematics , volume=

    Recognition of tree metrics , author=. SIAM Journal on Discrete Mathematics , volume=. 1990 , publisher=

    1990

  19. [19]

    47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) , year=

    Graph realization of distance sets , author=. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) , year=

    2022

  20. [20]

    Information Processing Letters , volume=

    On max-flow min-cut and integral flow properties for multicommodity flows in directed networks , author=. Information Processing Letters , volume=. 1989 , publisher=

    1989

  21. [21]

    arXiv preprint arXiv:2202.05127 , year=

    Improved Compression of the Okamura-Seymour Metric , author=. arXiv preprint arXiv:2202.05127 , year=

    Pith/arXiv arXiv

  22. [22]

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

    On the structure of unique shortest paths in graphs , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  23. [23]

    Journal of Graph Theory , volume=

    Irreducible nonmetrizable path systems in graphs , author=. Journal of Graph Theory , volume=. 2023 , publisher=

    2023

  24. [24]

    Discrete & Computational Geometry , volume=

    Geodesic geometry on graphs , author=. Discrete & Computational Geometry , volume=. 2022 , publisher=

    2022

  25. [25]

    arXiv preprint arXiv:2211.07042 , year=

    A local-to-global theorem for congested shortest paths , author=. arXiv preprint arXiv:2211.07042 , year=

    Pith/arXiv arXiv

  26. [26]

    Combinatorica , volume=

    The geometry of graphs and some of its algorithmic applications , author=. Combinatorica , volume=. 1995 , publisher=

    1995

  27. [27]

    Journal of the ACM (JACM) , volume=

    Polynomial flow-cut gaps and hardness of directed cut problems , author=. Journal of the ACM (JACM) , volume=. 2009 , publisher=

    2009

  28. [28]

    Advances in Mathematics , volume=

    Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces , author=. Advances in Mathematics , volume=. 1984 , publisher=

    1984

  29. [29]

    Journal of combinatorial theory , volume=

    A note on the tree realizability of a distance matrix , author=. Journal of combinatorial theory , volume=. 1969 , publisher=

    1969

  30. [30]

    A note on the metric properties of trees , author=. J. Combin. Theory Ser. B , volume=

  31. [31]

    Information Processing Letters , volume=

    Recognizing and realizing cactus metrics , author=. Information Processing Letters , volume=. 2020 , publisher=

    2020

  32. [32]

    2015 , publisher=

    Graph-theoretical matrices in chemistry , author=. 2015 , publisher=

    2015

  33. [33]

    Journal of the Royal Statistical Society: Series A (General) , volume=

    A review of hierarchical classification , author=. Journal of the Royal Statistical Society: Series A (General) , volume=. 1987 , publisher=

    1987

  34. [34]

    Journal of Computer and System Sciences , volume=

    Distance realization problems with applications to internet tomography , author=. Journal of Computer and System Sciences , volume=. 2001 , publisher=

    2001

  35. [35]

    2012 , publisher=

    Basic phylogenetic combinatorics , author=. 2012 , publisher=

    2012

  36. [36]

    Quarterly of applied mathematics , volume=

    Distance matrix of a graph and its realizability , author=. Quarterly of applied mathematics , volume=

  37. [37]

    Proceedings of Colloquia Mathematica Societatis Janos Bolyai , volume=

    How to tidy up your set-system , author=. Proceedings of Colloquia Mathematica Societatis Janos Bolyai , volume=

  38. [38]

    A Fourier-f

    Farkas, Gyula , journal=. A Fourier-f

  39. [39]

    arXiv preprint arXiv:1711.01370 , year=

    On constant multi-commodity flow-cut gaps for directed minor-free graphs , author=. arXiv preprint arXiv:1711.01370 , year=

    Pith/arXiv arXiv

  40. [40]

    2003 , publisher=

    Combinatorial optimization: polyhedra and efficiency , author=. 2003 , publisher=

    2003

  41. [41]

    Planar Emulators for Monge Matrices , booktitle =

    Hsien. Planar Emulators for Monge Matrices , booktitle =

  42. [42]

    2020 , url =

    Gramoz Goranci and Monika Henzinger and Pan Peng , title =. 2020 , url =

    2020

  43. [43]

    SIAM Journal on Discrete Mathematics , volume=

    Preserving terminal distances using minors , author=. SIAM Journal on Discrete Mathematics , volume=. 2014 , publisher=

    2014

  44. [44]

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

    Almost-linear -emulators for planar graphs , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  45. [45]

    arXiv preprint arXiv:2310.07857 , year=

    On (1+eps) -Approximate Flow Sparsifiers , author=. arXiv preprint arXiv:2310.07857 , year=

    Pith/arXiv arXiv

  46. [46]

    Discrete Mathematics , volume=

    Realizing symmetric set functions as hypergraph cut capacity , author=. Discrete Mathematics , volume=. 2016 , publisher=

    2016

  47. [47]

    Discrete Mathematics , volume=

    Realization of set functions as cut functions of graphs and hypergraphs , author=. Discrete Mathematics , volume=. 2001 , publisher=

    2001

  48. [48]

    , author=

    Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. , author=. Soda , volume=. 1993 , organization=

    1993

  49. [49]

    Shiva Chaudhuri and K. V. Subrahmanyam and Frank Wagner and Christos D. Zaroliagis , title =. Algorithmica , volume =. 2000 , url =

    2000

  50. [50]

    Combinatorica , volume=

    A factor 2 approximation algorithm for the generalized Steiner network problem , author=. Combinatorica , volume=. 2001 , publisher=

    2001

  51. [51]

    2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=

    Representative sets and irrelevant vertices: New tools for kernelization , author=. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=. 2012 , organization=

    2012

  52. [52]

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

    Vertex sparsification for edge connectivity , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  53. [53]

    arXiv preprint arXiv:2011.15101 , year=

    Vertex sparsification for edge connectivity in polynomial time , author=. arXiv preprint arXiv:2011.15101 , year=

    Pith/arXiv arXiv 2011

  54. [54]

    2001 , publisher=

    Hereditarily optimal realizations: Why are they relevant in phylogenetic analysis, and how does one compute them , author=. 2001 , publisher=

    2001

  55. [55]

    Annals of Combinatorics , volume=

    Hereditarily optimal realizations of consistent metrics , author=. Annals of Combinatorics , volume=. 2006 , publisher=

    2006

  56. [56]

    Discrete & Computational Geometry , volume=

    Concerning the relationship between realizations and tight spans of finite metrics , author=. Discrete & Computational Geometry , volume=. 2007 , publisher=

    2007

  57. [57]

    the electronic journal of combinatorics , volume=

    Characterizing cell-decomposable metrics , author=. the electronic journal of combinatorics , volume=

  58. [58]

    Discrete Applied Mathematics , volume=

    Optimal realizations and the block decomposition of a finite metric space , author=. Discrete Applied Mathematics , volume=. 2021 , publisher=

    2021

  59. [59]

    European Journal of Combinatorics , volume=

    T-theory: an overview , author=. European Journal of Combinatorics , volume=. 1996 , publisher=

    1996

  60. [60]

    Computer Science Review , volume=

    Graph spanners: A tutorial review , author=. Computer Science Review , volume=. 2020 , publisher=

    2020

  61. [61]

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

    The expander hierarchy and its applications to dynamic graph algorithms , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  62. [62]

    under submission , year=

    On (1 + eps)-Approximate Flow Sparsifiers , author=. under submission , year=

  63. [63]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Fast dynamic cuts, distances and effective resistances via vertex sparsifiers , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    2020

  64. [64]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Fully dynamic spectral vertex sparsifiers and applications , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  65. [65]

    Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25--26, 2016, Revised Selected Papers , pages=

    Vertex sparsification in trees , author=. Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25--26, 2016, Revised Selected Papers , pages=. 2017 , organization=

    2016

  66. [66]

    European Journal of Combinatorics , volume=

    Optimal realizations of generic five-point metrics , author=. European Journal of Combinatorics , volume=. 2009 , publisher=

    2009

  67. [67]

    arXiv preprint arXiv:2102.05077 , year=

    The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis , author=. arXiv preprint arXiv:2102.05077 , year=

    Pith/arXiv arXiv

  68. [68]

    Journal of Computer and System Sciences , volume=

    Characterizing multiterminal flow networks and computing flows in networks of small treewidth , author=. Journal of Computer and System Sciences , volume=. 1998 , publisher=

    1998

  69. [69]

    On the evolution of random graphs , author=. Publ. Math. Inst. Hung. Acad. Sci , volume=

  70. [70]

    Information Processing Letters , volume=

    On mimicking networks representing minimum terminal cuts , author=. Information Processing Letters , volume=. 2014 , publisher=

    2014

  71. [71]

    arXiv preprint arXiv:1706.06086 , year=

    An exponential lower bound for cut sparsifiers in planar graphs , author=. arXiv preprint arXiv:1706.06086 , year=

    Pith/arXiv arXiv

  72. [72]

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

    Mimicking networks and succinct representations of terminal cuts , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  73. [73]

    arXiv preprint arXiv:1702.01136 , year=

    Improved guarantees for vertex sparsification in planar graphs , author=. arXiv preprint arXiv:1702.01136 , year=

    Pith/arXiv arXiv

  74. [74]

    arXiv preprint arXiv:1702.05951 , year=

    Refined vertex sparsifiers of planar graphs , author=. arXiv preprint arXiv:1702.05951 , year=

    Pith/arXiv arXiv

  75. [75]

    , author=

    Delta-Wye-Delta transformations: algorithms and applications. , author=

  76. [76]

    Foundations of Computer Science, 2009

    Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size , author=. Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on , pages=. 2009 , organization=

    2009

  77. [77]

    SIAM Journal on Computing , volume=

    Vertex sparsification and oblivious reductions , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  78. [78]

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

    An improved approximation algorithm for the 0-extension problem , author=. Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2003 , organization=

    2003

  79. [79]

    Journal of the ACM (JACM) , volume=

    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms , author=. Journal of the ACM (JACM) , volume=. 1999 , publisher=

    1999

  80. [80]

    Flows, Cuts and Integral Routing in Graphs - an Approximation Algorithmist's Perspective , author=. Proc. of the International Congress of Mathematicians , volume=. 2016 , publisher=

    2016

Showing first 80 references.