pith. sign in

arxiv: 2606.25827 · v1 · pith:LJ4TOGQYnew · submitted 2026-06-24 · 💻 cs.DS

Paths and Intersections: Recognizing Outerplanar Metrics

Yu Chen , Zihan Tan This is my paper

Pith reviewed 2026-06-25 19:46 UTC · model grok-4.3

classification 💻 cs.DS
keywords outerplanar graphsdistance realizationmetric recognitionpolynomial algorithmpaths and intersectionsterminal distancesgraph metrics
0
0 comments X

The pith

A polynomial-time algorithm decides whether a given metric on terminals is realized by some outerplanar graph.

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

The paper considers the problem of determining whether distances specified on a terminal set T can be reproduced exactly as shortest-path distances inside some edge-weighted outerplanar graph that contains T. It first establishes that no local characterization exists, meaning the property cannot be decided by checking for the presence or absence of a finite collection of forbidden distance patterns on small subsets. The main contribution is an algorithm that solves the decision problem in time polynomial in the size of T alone. Both the non-existence proof and the algorithm rest on representing the underlying graph structure in terms of paths and the patterns of their intersections.

Core claim

There is no local characterization for outerplanar metrics, in contrast to trees and Okamura-Seymour instances, yet the realization question admits an efficient algorithm whose running time is polynomial in the number of terminals; both results follow from analyzing graphs as collections of paths together with the combinatorial patterns formed by their intersections.

What carries the argument

The structural representation of graphs as paths and their intersections, which simultaneously rules out local characterizations and supplies the decomposition used by the recognition algorithm.

If this is right

  • The outerplanar metric realization problem is solvable in time polynomial solely in the number of terminals.
  • Outerplanar metrics admit no finite list of forbidden local distance patterns.
  • The paths-and-intersections viewpoint yields both a non-existence proof and a constructive algorithm for this graph class.

Where Pith is reading between the lines

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

  • The same decomposition technique may apply to distance realization questions for other minor-closed graph families.
  • Network-design problems whose solutions must be outerplanar could be solved by first checking realizability of the target distances.
  • Global intersection patterns rather than local distance constraints appear necessary for characterizing outerplanar embeddability of metrics.

Load-bearing premise

The path-and-intersection decomposition is sufficient to capture every outerplanar graph that could realize a given terminal metric.

What would settle it

An explicit terminal metric on which the algorithm outputs yes yet exhaustive search finds no outerplanar graph realizing the distances, or vice versa.

Figures

Figures reproduced from arXiv: 2606.25827 by Yu Chen, Zihan Tan.

Figure 1
Figure 1. Figure 1: A canonical outerplanar graph: terminals [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Contracting all points oi,j into a supernode o, and splitting at o to obtain two graphs. We first prove that, after contraction, the shortest-path distance metric on terminals stays the same. Consider a terminal sℓ ∈ S. For any oij , since dist(oij , tj ) = βj , dist(sℓ , oij ) ≥ dist(sℓ , tj ) − dist(oij , tj ) = αℓ + βj − βj = αℓ . 6 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of path switching [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The i-(j + 1) path P (blue), and the curve γ along it (dashed green line). Claim 11. C ⪰ C ′ . Proof. Consider any cut (¯i, ¯j). On the one hand, by definition, distC(¯i, ¯j) = P (t,t′): crosses (¯i,¯j) Ft,t′. On the other hand, we show that distC′(¯i, ¯j) ≤ P (t,t′): crosses (¯i,¯j) Ft,t′. Assume that (¯i, ¯j) cuts the boundary into two segments (named left and right). Consider the i-(j + 1) path, which w… view at source ↗
Figure 5
Figure 5. Figure 5: A canonical outerplanar graph: boundary segments [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Massaging an outerplanar graph into a canonical one. [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The subproblem Π[i, j]. The Si-Sj channel (black) is enforced. The dynamic programming algorithm. We now describe the algorithm for computing the entries in the dynamic programming table. The base case is the entries Π[i, i + 1] for all i ≤ k − 1. In these subproblems, there are no channels to add, and the shortest paths are: the ti-ti+1 shortest path is Si , the ti+1-ti+2 shortest path is Si+1; and the ti… view at source ↗
Figure 8
Figure 8. Figure 8: The construction of the final outerplanar graph and the shortest path structure. [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: An illustration of Case 5.1. and the two second subpaths may intersect once. We show that the intersections cannot both happen. Assume for contradiction that the tx1 -ti subpath and the tx2 -tℓ+1 subpath intersect at a segment Sz, and the tj+1-ty2 subpath and the tℓ-ty1 subpath intersect at a segment Sw. Case 5.3.1. Sz lies between tx2 and tℓ , and Sw lies between tℓ+1 and ty2 . In this case, (tx2 , ty2 ) … view at source ↗
Figure 10
Figure 10. Figure 10: The outerplanar graph realizing the metric [PITH_FULL_IMAGE:figures/full_fig_p024_10.png] view at source ↗
read the original abstract

We study the following distance realization problem: given a metric $D$ on a set $T$ of terminals, does there exist an (edge-weighted) outerplanar graph $G$, such that $T\subseteq V(G)$, and for every pair $t,t'\in T$, $\textsf{dist}_G(t,t')=D(t,t')$? We first prove that there is no ``local characterization'', forming a contrast with trees and Okamura-Seymour instances. Our main result is an efficient algorithm for this problem whose running time is polynomial in $|T|$. Both our proof and our algorithm utilize a recent new approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

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 / 3 minor

Summary. The paper studies the distance realization problem for outerplanar graphs: given a metric D on a terminal set T, decide whether there exists an edge-weighted outerplanar graph G with T ⊆ V(G) such that dist_G(t,t') = D(t,t') for all pairs. It proves that outerplanar metrics admit no local characterization (in contrast to trees and Okamura-Seymour instances) and gives a polynomial-time algorithm whose running time is polynomial in |T|. Both results rely on a structural decomposition that views the graph as paths and their intersections.

Significance. If the claims hold, the result is significant for metric realization problems in algorithmic graph theory: it supplies the first polynomial-time recognition procedure for outerplanar metrics and demonstrates that their realizability can depend on global conditions (explicitly witnessed by a parity-dependent family). The explicit dynamic-programming algorithm whose state space is bounded by O(|T|^4) configurations and the self-contained counterexample family for the no-local-characterization claim are concrete strengths that do not rely on external unproven statements. The path-intersection viewpoint may be reusable for other graph classes.

minor comments (3)
  1. Abstract: the running time is described only as 'polynomial in |T|'; adding an explicit reference to the O(|T|^4) bound derived from the DP state space would make the complexity claim immediately verifiable from the abstract.
  2. Section 1 (Introduction): the contrast with trees and Okamura-Seymour instances is stated but not quantified; a short sentence comparing the new algorithm's degree with the known linear-time tree-metric algorithm would help readers gauge the advance.
  3. The manuscript uses the phrase 'paths and their intersections' repeatedly; a single definitional paragraph early in the paper that fixes the precise meaning of an 'intersection configuration' would eliminate potential ambiguity for readers unfamiliar with the recent structural approach.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the recognition of its significance for metric realization problems, and the recommendation for minor revision. We are pleased that the polynomial-time algorithm, the counterexample family for the absence of a local characterization, and the path-intersection structural viewpoint were viewed as concrete strengths.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core contributions—an explicit dynamic-programming algorithm over a path-intersection decomposition with O(|T|^4) states and an explicit family of metrics witnessing the absence of any local characterization—are presented as self-contained constructions and proofs. No fitted parameters, self-referential definitions, or load-bearing self-citations appear in the derivation; the structural approach is introduced within the manuscript itself rather than presupposed via prior unverified claims. The result is therefore an independent algorithmic existence statement rather than a reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, background axioms, or newly postulated entities.

pith-pipeline@v0.9.1-grok · 5646 in / 935 out tokens · 23999 ms · 2026-06-25T19:46:36.402794+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

145 extracted references · 8 linked inside Pith

  1. [1]

    arXiv preprint arXiv:2507.09620 , year=

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

    arXiv

  2. [2]

    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

  3. [3]

    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=

  4. [4]

    arXiv preprint arXiv:1807.01478 , year=

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

    Pith/arXiv arXiv

  5. [5]

    1972 , publisher=

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

    1972

  6. [6]

    Quarterly of applied mathematics , volume=

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

  7. [7]

    Discrete mathematics , volume=

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

    1998

  8. [8]

    Linear algebra and its applications , volume=

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

    2014

  9. [9]

    Algorithmica , volume=

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

    2023

  10. [10]

    Discrete mathematics , volume=

    GRAPH REALIZATIONS , author=. Discrete mathematics , volume=

  11. [11]

    Linear Algebra and Its Applications , volume=

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

    1982

  12. [12]

    SIAM Journal on Discrete Mathematics , volume=

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

    1990

  13. [13]

    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

  14. [14]

    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

  15. [15]

    arXiv preprint arXiv:2202.05127 , year=

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

    arXiv

  16. [16]

    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

  17. [17]

    Journal of Graph Theory , volume=

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

    2023

  18. [18]

    Discrete & Computational Geometry , volume=

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

    2022

  19. [19]

    arXiv preprint arXiv:2211.07042 , year=

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

    arXiv

  20. [20]

    Combinatorica , volume=

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

    1995

  21. [21]

    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

  22. [22]

    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

  23. [23]

    Journal of combinatorial theory , volume=

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

    1969

  24. [24]

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

  25. [25]

    Information Processing Letters , volume=

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

    2020

  26. [26]

    2015 , publisher=

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

    2015

  27. [27]

    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

  28. [28]

    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

  29. [29]

    2012 , publisher=

    Basic phylogenetic combinatorics , author=. 2012 , publisher=

    2012

  30. [30]

    Quarterly of applied mathematics , volume=

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

  31. [31]

    Proceedings of Colloquia Mathematica Societatis Janos Bolyai , volume=

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

  32. [32]

    A Fourier-f

    Farkas, Gyula , journal=. A Fourier-f

  33. [33]

    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

  34. [34]

    2003 , publisher=

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

    2003

  35. [35]

    Planar Emulators for Monge Matrices , booktitle =

    Hsien. Planar Emulators for Monge Matrices , booktitle =

  36. [36]

    2020 , url =

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

    2020

  37. [37]

    SIAM Journal on Discrete Mathematics , volume=

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

    2014

  38. [38]

    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=

  39. [39]

    arXiv preprint arXiv:2310.07857 , year=

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

    arXiv

  40. [40]

    Discrete Mathematics , volume=

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

    2016

  41. [41]

    Discrete Mathematics , volume=

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

    2001

  42. [42]

    , author=

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

    1993

  43. [43]

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

    2000

  44. [44]

    Combinatorica , volume=

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

    2001

  45. [45]

    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

  46. [46]

    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

  47. [47]

    arXiv preprint arXiv:2011.15101 , year=

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

    arXiv 2011

  48. [48]

    2001 , publisher=

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

    2001

  49. [49]

    Annals of Combinatorics , volume=

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

    2006

  50. [50]

    Discrete & Computational Geometry , volume=

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

    2007

  51. [51]

    the electronic journal of combinatorics , volume=

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

  52. [52]

    Discrete Applied Mathematics , volume=

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

    2021

  53. [53]

    European Journal of Combinatorics , volume=

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

    1996

  54. [54]

    Computer Science Review , volume=

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

    2020

  55. [55]

    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

  56. [56]

    under submission , year=

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

  57. [57]

    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

  58. [58]

    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=

  59. [59]

    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

  60. [60]

    European Journal of Combinatorics , volume=

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

    2009

  61. [61]

    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=

    arXiv

  62. [62]

    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

  63. [63]

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

  64. [64]

    Information Processing Letters , volume=

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

    2014

  65. [65]

    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

  66. [66]

    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

  67. [67]

    arXiv preprint arXiv:1702.01136 , year=

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

    Pith/arXiv arXiv

  68. [68]

    arXiv preprint arXiv:1702.05951 , year=

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

    arXiv

  69. [69]

    , author=

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

  70. [70]

    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

  71. [71]

    SIAM Journal on Computing , volume=

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

    2013

  72. [72]

    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

  73. [73]

    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

  74. [74]

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

    2016

  75. [75]

    Foundations of Computer Science, 2002

    Minimizing congestion in general networks , author=. Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on , pages=. 2002 , organization=

    2002

  76. [76]

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

    Extensions and limits to vertex sparsification , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=. 2010 , organization=

    2010

  77. [77]

    Journal of the ACM (JACM) , volume=

    Expander flows, geometric embeddings and graph partitioning , author=. Journal of the ACM (JACM) , volume=. 2009 , publisher=

    2009

  78. [78]

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

    Vertex sparsifiers and abstract rounding algorithms , author=. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=. 2010 , organization=

    2010

  79. [79]

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

    Metric extension operators, vertex sparsifiers and lipschitz extendability , author=. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=. 2010 , organization=

    2010

  80. [80]

    SIAM Journal on Computing , volume=

    Vertex sparsifiers: New results from old techniques , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

Showing first 80 references.