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

DOI10.1007/11830924_9zbMath1155.68394MaRDI QIDQ3595405

Goran Konjevod, Andréa W. Richa, T.-H. Hubert Chan, Donglin Xia

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

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

Cutting Corners Cheaply, or How to Remove Steiner Points, Terminal embeddings