The full Steiner tree problem

DOI10.1016/S0304-3975(03)00209-3zbMath1061.68121OpenAlexW2025002613MaRDI QIDQ702772

Chuan Yi Tang, Richard Chia-Tung Lee, Chin Lung Lu

Publication date: 18 January 2005

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00209-3

zbMATH Keywords

NP-completePhylogenetic treeMAX SNP-hardApproximation algorithmq17 68q25 68w25Evolutionary treeFull Steiner tree problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

On the terminal connection problem, A better constant-factor approximation for selected-internal Steiner minimum tree, A tutorial on the balanced minimum evolution problem, On the computational difficulty of the terminal connection problem, An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2, On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems, A polylogarithmic approximation for computing non-metric terminal Steiner trees, A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem, (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree, An Efficient Approximation Algorithm for the Steiner Tree Problem, Algorithms for the minimum diameter terminal Steiner tree problem, The Bursty Steiner Tree Problem, Algorithms for terminal Steiner trees, The Euclidean bottleneck full Steiner tree problem, The minimum evolution problem: Overview and classification, Approximating the selected-internal Steiner tree, 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, Upper and lower bounding strategies for the generalized minimum spanning tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm for full Steiner trees
• The Steiner problem with edge lengths 1 and 2
• The Steiner problem in phylogeny is NP-complete
• Optimization, approximation, and complexity classes
• The Steiner tree problem
• 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
• Algorithms on Strings, Trees and Sequences
• Thek-Steiner Ratio in Graphs
• The computation of nearly minimal Steiner trees in graphs