Space lower bounds for low-stretch greedy embeddings

DOI10.1016/j.tcs.2015.02.003zbMath1333.68027OpenAlexW2173558458MaRDI QIDQ896692

Ioannis Caragiannis, Christos Kalaitzis

Publication date: 10 December 2015

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

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

zbMATH Keywords

routingstretchgreedy embeddings

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Some results on greedy embeddings in metric spaces
• A linear lower bound on the unbounded error probabilistic communication complexity.
• The geometry of graphs and some of its algorithmic applications
• Monotone maps, sphericity and bounded second eigenvalue
• On a conjecture related to geometric routing
• A trade-off between space and efficiency for routing tables
• Ordinal embeddings of minimum relaxation
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry
• Lower Bounds for Approximation by Nonlinear Manifolds