A Tight Lower Bound for the Steiner Point Removal Problem on Trees
From MaRDI portal
Publication:3595405
DOI10.1007/11830924_9zbMath1155.68394MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm, Unnamed Item, Unnamed Item, Distance-Preserving Graph Contractions, Refined Vertex Sparsifiers of Planar Graphs, Improved Guarantees for Vertex Sparsification in Planar Graphs, Distance-Preserving Graph Contractions, Cutting Corners Cheaply, or How to Remove Steiner Points, Approximating spaces of Nagata dimension zero by weighted trees, Terminal embeddings