On the approximability of the Steiner tree problem in phylogeny

DOI10.1016/S0166-218X(98)00069-9zbMath0927.68060MaRDI QIDQ1281766

Jens Lagergren, David Fernández Baca

Publication date: 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Steiner tree problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99)

Related Items (2)

On the low-dimensional Steiner minimum tree problem in Hamming metric ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The computational complexity of inferring rooted phylogenies by parsimony
• The Steiner problem in phylogeny is NP-complete
• Optimization, approximation, and complexity classes
• Convex tree realizations of partitions
• The Steiner tree problem
• The complexity of reconstructing trees from qualitative characters and subtrees
• Approximation algorithms for combinatorial problems
• An idealized concept of the true cladistic character
• Aligning sequences via an evolutionary tree
• Improved Approximations for the Steiner Tree Problem
• Two strikes against perfect phylogeny

This page was built for publication: On the approximability of the Steiner tree problem in phylogeny