A Tight Lower Bound for the Steiner Point Removal Problem on Trees

DOI10.1007/11830924_9MaRDI QIDQ3595405zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

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)