A better constant-factor approximation for selected-internal Steiner minimum tree

DOI10.1007/s00453-009-9301-8zbMath1187.68713OpenAlexW2143095751MaRDI QIDQ848949

Weili Wu, Donghyun Kim, Feng Zou, Yaochun Huang, Xianyue Li

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9301-8

zbMATH Keywords

approximation algorithmselected-internal Steiner tree

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ Algorithms for the minimum diameter terminal Steiner tree problem ⋮ On the Clustered Steiner Tree Problem ⋮ On the clustered Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The full Steiner tree problem
• Approximating the selected-internal Steiner tree
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• The Steiner problem in phylogeny is NP-complete
• The Steiner tree problem
• On the terminal Steiner tree problem.
• On component-size bounded Steiner trees
• Algorithms for terminal Steiner trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Thek-Steiner Ratio in Graphs