Ramsey Spanning Trees and Their Applications

DOI10.1145/3371039zbMath1403.05028arXiv1707.08769OpenAlexW3011280253MaRDI QIDQ4607997

Shiri Chechik, Ofer Neiman, Ittai Abraham, Arnold Filtser, Michael Elkin

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

zbMATH Keywords

distortioncompact routingdistance oraclesspanning treesmetric embeddingmetric Ramsey problemtree-padding spanner

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Generalized Ramsey theory (05C55) Data structures (68P05) Metric embeddings as related to computational problems and algorithms (68R12)

Related Items (6)

Covering metric spaces by few trees ⋮ Unnamed Item ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Graph spanners: a tutorial review ⋮ Covering Metric Spaces by Few Trees ⋮ Light spanners for high dimensional norms via stochastic decompositions

This page was built for publication: Ramsey Spanning Trees and Their Applications