The complexity of phylogeny constraint satisfaction

DOI10.4230/LIPICS.STACS.2016.20MaRDI QIDQ4601872zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Peter Jonsson, Trung van Pham

Publication date 24 January 2018

Full work available at URL http://dblp.uni-trier.de/db/journals/corr/corr1503.html#BodirskyJP15

zbMATH Keywords

computational complexityconstraint satisfaction problemsmodel theoryphylogenetic reconstructionRamsey theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

Recommendations

• The complexity of phylogeny constraint satisfaction problems
• The Complexity of Rooted Phylogeny Problems
• Counting consistent phylogenetic trees is \#P-complete
• Algorithms for phylogeny reconstruction in a new mathematical model
• Extension operations on sets of leaf-labelled trees

Cited in

(16)

• Phylogenetic flexibility via Hall-type inequalities and submodularity
• Unique perfect phylogeny is intractable
• On the hardness of inferring phylogenies from triplet-dissimilarities
• Inferring phylogenetic trees using answer set programming
• The Complexity of Rooted Phylogeny Problems
• A dichotomy for first-order reducts of unary structures
• The language of stratified sets is confluent and strongly normalising
• Deciding the closure of inconsistent rooted triples is NP-complete
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• Time complexity of constraint satisfaction via universal algebra
• An initial study of time complexity in infinite-domain constraint satisfaction
• The Worst Case Complexity of Maximum Parsimony
• The complexity of phylogeny constraint satisfaction problems
• Constructing Camin-Sokal Phylogenies Via Answer Set Programming
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees

This page was built for publication: The complexity of phylogeny constraint satisfaction

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