Approximating the selected-internal Steiner tree

DOI10.1016/j.tcs.2007.05.035zbMath1188.68356OpenAlexW2050428285MaRDI QIDQ995588

Shih-Cheng Yang, Sun-Yuan Hsieh

Publication date: 3 September 2007

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

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

zbMATH Keywords

approximation algorithmsSteiner treedesign and analysis of algorithmsMAX SNP-hardthe selected-internal Steiner tree problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Approximation algorithms (68W25)

Related Items (7)

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 ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree ⋮ Algorithms for the minimum diameter terminal Steiner tree problem ⋮ On the Clustered Steiner Tree Problem ⋮ On the clustered Steiner tree problem

Cites Work

• The full Steiner tree problem
• The Steiner problem in phylogeny is NP-complete
• On component-size bounded Steiner trees
• Advances in Steiner trees
• Proof verification and the hardness of approximation problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Faster exact algorithms for steiner trees in planar networks
• Thek-Steiner Ratio in Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating the selected-internal Steiner tree