The complexity of phylogeny constraint satisfaction
DOI10.4230/LIPICS.STACS.2016.20zbMATH Open1388.68101OpenAlexW2963913303MaRDI QIDQ4601872FDOQ4601872
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
Recommendations
computational complexityRamsey theoryconstraint satisfaction problemsmodel theoryphylogenetic reconstruction
Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (16)
- Phylogenetic flexibility via Hall-type inequalities and submodularity
- Time complexity of constraint satisfaction via universal algebra
- On the hardness of inferring phylogenies from triplet-dissimilarities
- A dichotomy for first-order reducts of unary structures
- The complexity of phylogeny constraint satisfaction problems
- Title not available (Why is that?)
- Deciding the closure of inconsistent rooted triples is NP-complete
- The Worst Case Complexity of Maximum Parsimony
- Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Inferring phylogenetic trees using answer set programming
- Unique perfect phylogeny is intractable
- The language of stratified sets is confluent and strongly normalising
- Constructing Camin-Sokal Phylogenies Via Answer Set Programming
- An initial study of time complexity in infinite-domain constraint satisfaction
- The Complexity of Rooted Phylogeny Problems
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)
