The full Steiner tree problem

DOI10.1016/S0304-3975(03)00209-3MaRDI QIDQ702772zbMATH OpenOpenAlexFDO

Authors Chin Lung Lu, Chuan Yi Tang, R. C. T. Lee

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)

Recommendations

• scientific article; zbMATH DE number 2089965
• On the hardness of full Steiner tree problems
• On the full and bottleneck full Steiner tree problems
• On the approximability of the Steiner tree problem in phylogeny
• On the approximability of the Steiner tree problem in phylogeny

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• A linear time algorithm for full Steiner trees
• Advances in Steiner trees
• Algorithms on Strings, Trees and Sequences
• Optimization, approximation, and complexity classes
• Proof verification and the hardness of approximation problems
• The Complexity of Computing Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Steiner problem in phylogeny is NP-complete
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• The computation of nearly minimal Steiner trees in graphs
• Thek-Steiner Ratio in Graphs

Cited in

(30)

• On the terminal connection problem
• On the full and bottleneck full Steiner tree problems
• A polylogarithmic approximation for computing non-metric terminal Steiner trees
• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
• The Euclidean bottleneck full Steiner tree problem
• On full Steiner trees in unit disk graphs
• On the computational difficulty of the terminal connection problem
• scientific article; zbMATH DE number 2089965 (Why is no real title available?)
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Binary Steiner trees: structural results and an exact solution approach
• Steiner tree problems
• On the clustered Steiner tree problem
• The Steiner tree problem
• On the clustered Steiner tree problem
• A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem
• A multivariate analysis of the strict terminal connection problem
• On the approximability of the Steiner tree problem in phylogeny
• An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2
• Algorithms for terminal Steiner trees
• scientific article; zbMATH DE number 1424546 (Why is no real title available?)
• The minimum evolution problem: Overview and classification
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• The 1-steiner tree problem
• Algorithms for the minimum diameter terminal Steiner tree problem
• On the hardness of full Steiner tree problems
• The bursty Steiner tree problem
• A better constant-factor approximation for selected-internal Steiner minimum tree
• Approximating the selected-internal Steiner tree
• A tutorial on the balanced minimum evolution problem
• Upper and lower bounding strategies for the generalized minimum spanning tree problem

This page was built for publication: The full Steiner tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q702772)