A Tight Lower Bound for the Steiner Point Removal Problem on Trees
DOI10.1007/11830924_9zbMATH Open1155.68394OpenAlexW2157338838MaRDI QIDQ3595405FDOQ3595405
Authors: T.-H. Hubert Chan, Donglin Xia, Goran Konjevod, Andrea Richa 
Publication date: 28 August 2007
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11830924_9
Recommendations
- Steiner point removal with distortion \(O(\log k)\)
- Cutting corners cheaply, or how to remove Steiner points
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Steiner point removal -- distant terminals don't (really) bother
- Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (15)
- Distance-Preserving Graph Contractions
- Distance-Preserving Graph Contractions
- Narrow-Shallow-Low-Light Trees with and without Steiner Points
- Improved guarantees for vertex sparsification in planar graphs
- Near-optimal distance emulator for planar graphs
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Terminal embeddings
- Steiner point removal -- distant terminals don't (really) bother
- Steiner point removal with distortion \(O(\log k)\)
- Online Spanners in Metric Spaces
- Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
- Approximating spaces of Nagata dimension zero by weighted trees
- Improved guarantees for vertex sparsification in planar graphs
- Refined vertex sparsifiers of planar graphs
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
This page was built for publication: A Tight Lower Bound for the Steiner Point Removal Problem on Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3595405)
