A Tight Lower Bound for the Steiner Point Removal Problem on Trees
From MaRDI portal
Publication:3595405
DOI10.1007/11830924_9zbMath1155.68394OpenAlexW2157338838MaRDI QIDQ3595405
Donglin Xia, T.-H. Hubert Chan, Goran Konjevod, Andréa W. 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
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)
Related Items (12)
Terminal embeddings ⋮ Approximating spaces of Nagata dimension zero by weighted trees ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Online Spanners in Metric Spaces ⋮ Unnamed Item ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Distance-Preserving Graph Contractions ⋮ Distance-Preserving Graph Contractions ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points
This page was built for publication: A Tight Lower Bound for the Steiner Point Removal Problem on Trees