Algorithms for terminal Steiner trees

DOI10.1016/j.tcs.2007.08.001zbMath1143.68061OpenAlexW1989076933MaRDI QIDQ2465633

Yanyan Li

Publication date: 7 January 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.08.001

zbMATH Keywords

approximation algorithmsterminal Steiner trees

Mathematics Subject Classification ID

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

Related Items

A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ 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 ⋮ 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

• The full Steiner tree problem
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• The Steiner problem with edge lengths 1 and 2
• On the terminal Steiner tree problem.
• On the Full and Bottleneck Full Steiner Tree Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Tighter Bounds for Graph Steiner Tree Approximation