Deciding the closure of inconsistent rooted triples is NP-complete

DOI10.4230/LIPICS.ISAAC.2018.12MaRDI QIDQ5091002FDOQ5091002

Authors: Matthew P. Johnson 

Publication date: 21 July 2022

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

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

zbMATH Keywords

computational complexitydirected hypergraphsNP-completenessphylogenetic treesacyclic induced subgraphsrooted triple entailment

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• 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)