Covering Metric Spaces by Few Trees

DOI10.4230/LIPIcs.ICALP.2019.20OpenAlexW2965645264MaRDI QIDQ5091169

Nova Fandina, Ofer Neiman, Yair Bartal

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1905.07559

zbMATH Keywords

tree coverprobabilistic hierarchical familyRamsey tree cover

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

Covering metric spaces by few trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey partitions and proximity data structures
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On metric Ramsey-type phenomena
• Geometric Spanner Networks
• A constructive proof of the general lovász local lemma
• Lower-stretch spanning trees
• Spanners and emulators with sublinear distance errors
• Oblivious network design
• Complexity of network synchronization
• Graph spanners
• Applications of a Planar Separator Theorem
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Ramsey Spanning Trees and Their Applications
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• A trade-off between space and efficiency for routing tables
• Generating sparse spanners for weighted graphs
• Approximate distance oracles
• Object location using path separators
• Metric embedding via shortest path decompositions
• Excluded minors, network decomposition, and multicommodity flow
• Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
• Deformable spanners and applications
• A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
• Using petal-decompositions to build a low stretch spanning tree
• Compact oracles for reachability and approximate distances in planar digraphs
• Algorithms – ESA 2004
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Advances in metric embedding theory
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Covering Metric Spaces by Few Trees