Covering metric spaces by few trees
From MaRDI portal
Publication:2168848
DOI10.1016/j.jcss.2022.06.001OpenAlexW2946166375MaRDI QIDQ2168848
Ora Nova Fandina, Ofer Neiman, Yair Bartal
Publication date: 26 August 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2022.06.001
Cites Work
- Unnamed Item
- 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
- On sparse spanners of weighted graphs
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- 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
- Covering Metric Spaces by Few Trees
- Approximate distance oracles
- Object location using path separators
- Excluded minors, network decomposition, and multicommodity flow
- Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
- Algorithm Theory - SWAT 2004
- 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
- Algorithms and Computation
- A tight bound on approximating arbitrary metrics by tree metrics