The internal Steiner tree problem: Hardness and approximations

DOI10.1016/j.jco.2012.08.005zbMath1256.68131OpenAlexW1967576404MaRDI QIDQ1931427

Chia-Wei Lee, Huang-Ming Gao, Sun-Yuan Hsieh, Chao-Wen Huang

Publication date: 14 January 2013

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2012.08.005

zbMATH Keywords

approximation algorithmsSteiner treesVLSI routingdesign and analysis of algorithmsMAX SNP-hardnessthe internal Steiner tree problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (6)

An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ Reliability assessment of the divide-and-swap cube in terms of generalized connectivity ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ On the Clustered Steiner Tree Problem ⋮ On the clustered Steiner tree problem

This page was built for publication: The internal Steiner tree problem: Hardness and approximations