Finding a maximum compatible tree is NP-hard for sequences and trees

DOI10.1016/0893-9659(96)00012-2zbMath0852.92015OpenAlexW1998131269MaRDI QIDQ1921170

Angèle M. Hamel, Mike A. Steel

Publication date: 11 August 1996

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

Full work available at URL: http://hdl.handle.net/10092/11127

zbMATH Keywords

sequencesNP-hardDNA sequencescompatibilityphylogenetic analysisleaf-labelled treesaligned 2-state sequences

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Complexity and performance of numerical algorithms (65Y20)

Related Items (4)

Maximum agreement and compatible supertrees ⋮ On the complexity of comparing evolutionary trees ⋮ Beyond evolutionary trees ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems

Cites Work

• Convex tree realizations of partitions
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Efficient algorithms for inferring evolutionary trees
• Unnamed Item

This page was built for publication: Finding a maximum compatible tree is NP-hard for sequences and trees