Cuts, trees and \(\ell_1\)-embeddings of graphs
From MaRDI portal
Publication:705742
DOI10.1007/s00493-004-0015-xzbMath1056.05040OpenAlexW48861618WikidataQ60608702 ScholiaQ60608702MaRDI QIDQ705742
Yuri Rabinovich, Ilan Newman, Alistair Sinclair, Anupam Gupta
Publication date: 14 February 2005
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-004-0015-x
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A note on multiflows and treewidth, Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs, Coarse differentiation and multi-flows in planar graphs, A CODING OF BUNDLE GRAPHS AND THEIR EMBEDDINGS INTO BANACH SPACES, Metric Embedding via Shortest Path Decompositions, A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time, Markov type and threshold embeddings, On the geometry of the countably branching diamond graphs, Non-greedy online Steiner trees on outerplanar graphs, Metric embeddings of Laakso graphs into Banach spaces, Stochastic approximation of lamplighter metrics, 𝐿₁-distortion of Wasserstein metrics: A tale of two dimensions, Cut-sufficient directed 2-commodity multiflow topologies, An introduction to the Ribe program, Distortion of embeddings of binary trees into diamond graphs, Lipschitz-free Spaces on Finite Metric Spaces, Maximum gradient embeddings and monotone clustering, \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees, Unnamed Item, Non-greedy Online Steiner Trees on Outerplanar Graphs, Pathwidth, trees, and random embeddings, Unnamed Item, A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional, Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs, Isometric embedding of Busemann surfaces into \(L_1\), An exact algorithm for minimum distortion embedding, Slightly Superexponential Parameterized Problems, Randomly removing \(g\) handles at once, Impossibility of dimension reduction in the nuclear norm, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators, A node-capacitated Okamura-Seymour theorem, Analysis on Laakso graphs with application to the structure of transportation cost spaces, Multicommodity flows and cuts in polymatroidal networks, DIAMOND GRAPHS AND SUPER-REFLEXIVITY, Isometric structure of transportation cost spaces on finite metric spaces, On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$, Unnamed Item
