Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm
From MaRDI portal
Publication:4634019
DOI10.1137/18M1184400zbMath1411.68079arXiv1808.02800MaRDI QIDQ4634019
Publication date: 7 May 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.02800
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph minors (05C83) Distance in graphs (05C12)
Related Items
Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Online Spanners in Metric Spaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved approximation algorithm for requirement cut
- Terminal embeddings
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Preserving Terminal Distances Using Minors
- Extensions and limits to vertex sparsification
- Prioritized Metric Structures and Embedding
- Approximate distance oracles
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Graph spanners
- On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Steiner Point Removal --- Distant Terminals Don't (Really) Bother
- Approximation Algorithms for the 0-Extension Problem
- Twice-Ramanujan Sparsifiers
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Refined Vertex Sparsifiers of Planar Graphs
- Fibonacci heaps and their uses in improved network optimization algorithms
- Small Stretch Pairwise Spanners
- Towards (1 + ∊)-Approximate Flow Sparsifiers
- On vertex sparsifiers with Steiner nodes
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Automata, Languages and Programming
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Vertex Sparsifiers: New Results from Old Techniques
- A tight bound on approximating arbitrary metrics by tree metrics
