The geometry of graphs and some of its algorithmic applications

DOI10.1007/BF01200757zbMath0827.05021OpenAlexW2176446742WikidataQ105824835 ScholiaQ105824835MaRDI QIDQ1894703

Eran London, Yuri Rabinovich, Nathan Linial

Publication date: 24 July 1995

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200757

zbMATH Keywords

algorithmdecompositionembeddingnormed spacemulticommodity flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Geometry and structure of normed linear spaces (46B20) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the contact dimensions of graphs
• Isometric embedding in \(\ell_ p\)-spaces
• Proof of the squashed cube conjecture
• Minimum dimension embedding of finite metric spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Rubber bands, convex embeddings and graph connectivity
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• On sparse spanners of weighted graphs
• Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces
• Orthogonal representations and connectivity of graphs
• Geometrical embeddings of graphs
• Über zwei Probleme bezüglich konvexer Körper von P. Erdős und von V.L. Klee
• Cutting disjoint disks by straight lines
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Extensions of Lipschitz mappings into a Hilbert space
• On Isometric Embeddings of Graphs
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Graph spanners
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Local-Global Phenomena in Graphs
• Metric Transforms and Euclidean Embeddings
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Approximate max-flow min-(multi)cut theorems and their applications
• Feasibility of Two Commodity Network Flows
• Multi-Commodity Network Flows

Related Items (only showing first 100 items - show all)

Sketching and Embedding are Equivalent for Norms ⋮ Johnson–Lindenstrauss Embeddings with Kronecker Structure ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Metric Characterizations of Some Classes of Banach Spaces ⋮ Symmetric Graph Properties Have Independent Edges ⋮ The Range of Topological Effects on Communication ⋮ A smoothing majorization method for matrix minimization ⋮ How to Use Spanning Trees to Navigate in Graphs ⋮ A NOTE ON NON-AMENABILITY OF ℬ(ℓ_p) FOR p=1,2 ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Negative-type diversities, a multi-dimensional analogue of negative-type metrics ⋮ Lossless Prioritized Embeddings ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Prioritized Metric Structures and Embedding ⋮ Proximity-preserving labeling schemes ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Diversity-normed spaces and diversity embeddings ⋮ On spatial conditioning of the spectrum of discrete random Schrödinger operators ⋮ Stochastic approximation of lamplighter metrics ⋮ Spectral dimension, Euclidean embeddings, and the metric growth exponent ⋮ Least distortion Euclidean embeddings of flat tori ⋮ Random Projection Ensemble Classification with High-Dimensional Time Series ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ Approximating spaces of Nagata dimension zero by weighted trees ⋮ Polynomial growth and asymptotic dimension ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Norms of structured random matrices ⋮ Lipschitz-free Spaces on Finite Metric Spaces ⋮ Diversities and the generalized circumradius ⋮ Unnamed Item ⋮ Expander graphs and their applications ⋮ Interactions of computational complexity theory and mathematics ⋮ Representation and coding of signal geometry ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Single-Sink Multicommodity Flow with Side Constraints ⋮ Metric Curvatures Revisited: A Brief Overview ⋮ Euclidean distortion and the sparsest cut ⋮ Unnamed Item ⋮ Local and global expansion in random geometric graphs ⋮ Advances in metric embedding theory ⋮ The Geometry of Computation-Graph Abstraction ⋮ Combinatorial theorems about embedding trees on the real line ⋮ On the equivalence between low-rank matrix completion and tensor rank ⋮ Comparison of Metric Spectral Gaps ⋮ Low Distortion Metric Embedding into Constant Dimension ⋮ A semidefinite bound for mixing rates of Markov chains ⋮ Approximating Requirement Cut via a Configuration LP ⋮ L ^p -distortion and p -spectral gap of finite graphs ⋮ The intrinsic dimensionality of graphs ⋮ On dominated \(\ell_1\) metrics ⋮ On the dimension of trees ⋮ Spectral Techniques to Explore Point Clouds in Euclidean Space, with Applications to Collective Coordinates in Structural Biology ⋮ Unnamed Item ⋮ Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances ⋮ Towards a bilipschitz invariant theory ⋮ Inapproximability for metric embeddings into $\mathbb{R}^{d}$ ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Recovery of Low Rank Symmetric Matrices via Schatten p Norm Minimization ⋮ Cluster before you hallucinate: node-capacitated network design and energy efficient routing ⋮ Negative type and bi-Lipschitz embeddings into Hilbert space ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Book Review: Metric embeddings: bilipschitz and coarse embedddings into Banach spaces ⋮ Unnamed Item ⋮ Some applications of Ball’s extension theorem ⋮ Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Bandwidth and Low Dimensional Embedding ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Union of Euclidean Metric Spaces is Euclidean ⋮ DIAMOND GRAPHS AND SUPER-REFLEXIVITY ⋮ Compression functions of uniform embeddings of groups into Hilbert and Banach spaces ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁ ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ The legacy of Jean Bourgain in geometric functional analysis ⋮ Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization ⋮ The geometry of crashes. A measure of the dynamics of stock market crises ⋮ Braess's paradox in expanders ⋮ On linear convergence of projected gradient method for a class of affine rank minimization problems ⋮ Reconstructing an economic space from a market metric ⋮ Geometric complexity of embeddings in \(\mathbb R^d\) ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ A note on multiflows and treewidth ⋮ Metric violation distance: hardness and approximation ⋮ How to use spanning trees to navigate in graphs ⋮ Approximation and inapproximability results for maximum clique of disc graphs in high dimensions ⋮ Symmetric graph properties have independent edges ⋮ Topology-invariant similarity of nonrigid shapes ⋮ Coarse differentiation and multi-flows in planar graphs ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Approximation algorithms for requirement cut on graphs ⋮ Limitations to Fréchet's metric embedding method

This page was built for publication: The geometry of graphs and some of its algorithmic applications