Online Spanners in Metric Spaces
From MaRDI portal
Publication:6195959
DOI10.1137/22m1534572arXiv2202.09991MaRDI QIDQ6195959
Csaba D. Tóth, Hadi Khodabandeh, Arnold Filtser, Sujoy Bhore
Publication date: 14 March 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.09991
Analysis of algorithms (68W40) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ordered theta graphs
- On-line Steiner trees in the Euclidean plane
- Geometric spanners with applications in wireless networks
- Towards tight bounds on theta-graphs: more is not always better
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- On sparse spanners of weighted graphs
- Some low distortion metric Ramsey problems
- There are planar graphs almost as good as the complete graph
- On-line generalized Steiner problem
- Constructing light spanners deterministically in near-linear time
- Deformable spanners and applications
- Competitive concurrent distributed queuing
- A general approach to online network optimization problems
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Fully dynamic randomized algorithms for graph spanners
- Geometric Spanner Networks
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Graph Distances in the Data-Stream Model
- Graph spanners
- Dynamic Steiner Tree Problem
- Near-Optimal Light Spanners
- LAST but not Least: Online Spanners for Buy-at-Bulk
- Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- The Greedy Spanner Is Existentially Optimal
- Fast Constructions of Lightweight Spanners for General Graphs
- Approximate distance oracles for geometric spanners
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Euclidean Steiner Spanners: Light and Sparse
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
- Greedy spanners are optimal in doubling metrics
- Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Online Node-Weighted Steiner Tree and Related Problems
- Online Node-weighted Steiner Forest and Extensions via Disk Paintings
- Light Euclidean Spanners with Steiner Points
- Fully dynamic geometric spanners
- Online Euclidean Spanners
This page was built for publication: Online Spanners in Metric Spaces
