Bandwidth and low dimensional embedding

DOI10.1016/j.tcs.2013.05.038zbMath1301.05096OpenAlexW2015706743MaRDI QIDQ388456

Douglas E. Carroll, Yair Bartal, Adam Meyerson, Ofer Neiman

Publication date: 19 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.05.038

zbMATH Keywords

metric embeddingbandwithlow dimension

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Metric Embedding via Shortest Path Decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The metrical interpretation of superreflexivity in Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• The geometry of graphs and some of its algorithmic applications
• On the nonexistence of bilipschitz parameterizations and geometric problems about \(A_ \infty\)-weights
• On embedding trees into uniformly convex Banach spaces
• A constructive proof of the general lovász local lemma
• Embedding Bounded Bandwidth Graphs into ℓ1
• Plongements lipschitziens dans ${\bbfR}\sp n$
• The bandwidth problem for graphs and matrices—a survey
• An algorithmic approach to the Lovász local lemma. I
• A lower bound on the distortion of embedding planar metrics into Euclidean space