Bandwidth and Low Dimensional Embedding

DOI10.1007/978-3-642-22935-0_5zbMath1343.05146OpenAlexW2218766326MaRDI QIDQ3088081

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

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_5

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

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