On approximation algorithms for the terminal Steiner tree problem

DOI10.1016/j.ipl.2003.09.014zbMath1178.68677OpenAlexW1980288485MaRDI QIDQ1029037

Doratha E. Drake, Stefan Hougardy

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.09.014

zbMATH Keywords

approximation algorithmsSteiner tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (15)

DIAMETER-CONSTRAINED STEINER TREES ⋮ A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ On some network design problems with degree constraints ⋮ A polylogarithmic approximation for computing non-metric terminal Steiner trees ⋮ Minimum diameter cost-constrained Steiner trees ⋮ The minimum spanning tree problem with non-terminal set ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Algorithms for the minimum diameter terminal Steiner tree problem ⋮ On the hardness of full Steiner tree problems ⋮ Algorithms for terminal Steiner trees ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ A multivariate analysis of the strict terminal connection problem ⋮ On the Clustered Steiner Tree Problem ⋮ On full Steiner trees in unit disk graphs ⋮ On the clustered Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• On the terminal Steiner tree problem.
• On the Full and Bottleneck Full Steiner Tree Problems
• A threshold of ln n for approximating set cover
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

This page was built for publication: On approximation algorithms for the terminal Steiner tree problem