Ramsey Spanning Trees and Their Applications
From MaRDI portal
Publication:4607997
DOI10.1145/3371039zbMath1403.05028arXiv1707.08769MaRDI QIDQ4607997
Ofer Neiman, Michael Elkin, Shiri Chechik, Ittai Abraham, Arnold Filtser
Publication date: 15 March 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.08769
distortion; compact routing; distance oracles; spanning trees; metric embedding; metric Ramsey problem; tree-padding spanner
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C55: Generalized Ramsey theory
68P05: Data structures
68R12: Metric embeddings as related to computational problems and algorithms