Deciding the closure of inconsistent rooted triples is NP-complete

DOI10.4230/LIPICS.ISAAC.2018.12MaRDI QIDQ5091002FDO

Authors Matthew P. Johnson

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1807.00030

zbMATH Keywords

computational complexitydirected hypergraphsNP-completenessphylogenetic treesacyclic induced subgraphsrooted triple entailment

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• The Complexity of Rooted Phylogeny Problems
• The complexity of phylogeny constraint satisfaction problems
• New results on optimizing rooted triplets consistency
• New Results on Optimizing Rooted Triplets Consistency
• The complexity of phylogeny constraint satisfaction

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Directed hypergraphs and applications
• Extension operations on sets of leaf-labelled trees
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• On the complexity of testing for odd holes and induced odd paths

This page was built for publication: Deciding the closure of inconsistent rooted triples is NP-complete

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