The Steiner problem in phylogeny is NP-complete
From MaRDI portal
Publication:1167073
DOI10.1016/S0196-8858(82)80004-3zbMath0489.92002MaRDI QIDQ1167073
Ronald L. Graham, Les R. Foulds
Publication date: 1982
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Steiner problemNP-completenessHamming distanceprotein sequencesphylogenymaximum parsimonyminimal spanning treeevolutionary treeDNA structures
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) General biology and biomathematics (92B05) Physiological, cellular and medical topics (92Cxx)
Related Items
Testing the theory of evolution: A novel application of combinatorial optimization, The computational complexity of inferring rooted phylogenies by parsimony, Computational complexity of inferring phylogenies from dissimilarity matrices, Characterizing local optima for maximum parsimony, On component-size bounded Steiner trees, A better constant-factor approximation for selected-internal Steiner minimum tree, Is the protein model assignment problem under linked branch lengths NP-hard?, On the quirks of maximum parsimony and likelihood on phylogenetic networks, Mathematical aspects of phylogenetic groves, Fast heuristic algorithms for rectilinear Steiner trees, Cases in which ancestral maximum likelihood will be confusingly misleading, Tropical geometric variation of tree shapes, \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time, Combinatorial views on persistent characters in phylogenetics, On the low-dimensional Steiner minimum tree problem in Hamming metric, Probability Steiner trees and maximum parsimony in phylogenetic analysis, An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2, Optimizing phylogenetic supertrees using answer set programming, (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree, Walks in phylogenetic treespace, Topology reconstruction using time series data in telecommunication networks, Search-based structured prediction, PULLPRU: a practical approach to estimate phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion, Non-hereditary maximum parsimony trees, Groves of phylogenetic trees, Computing the blocks of a quasi-median graph, Regular Language Constrained Sequence Alignment Revisited, Inferring phylogenetic trees using answer set programming, On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric, Binary Steiner trees: structural results and an exact solution approach, On better heuristics for Steiner minimum trees, The complexity of reconstructing trees from qualitative characters and subtrees, Distributions on bicoloured binary trees arising from the principle of parsimony, Adaptive memory programming: local search parallel algorithms for phylogenetic tree construc\-tion, The full Steiner tree problem, A near linear time approximation scheme for Steiner tree among obstacles in the plane, Reconstructing evolution of sequences subject to recombination using parsimony, Approximating the selected-internal Steiner tree, Two strikes against perfect phylogeny, Quasi-median hulls in Hamming space are Steiner hulls, Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem, Most parsimonious likelihood exhibits multiple optima for compatible characters, A new recombination lower bound and the minimum perfect phylogenetic forest problem, On the approximability of the Steiner tree problem in phylogeny, Large-Scale Multiple Sequence Alignment and Phylogeny Estimation, Scatter search with path relinking for phylogenetic inference, On Computing the Maximum Parsimony Score of a Phylogenetic Network, An algorithm for the maximum likelihood problem on evolutionary trees, A survey on pairwise compatibility graphs, Matchings and phylogenetic trees, Landscapes on spaces of trees, Geometry of the space of phylogenetic trees, On the maximum parsimony distance between phylogenetic trees
Cites Work
