Counting consistent phylogenetic trees is \#P-complete

DOI10.1016/j.aam.2003.08.006zbMath1053.05029OpenAlexW2145844324MaRDI QIDQ1883389

Charles Semple, Magnus Bordewich, John Talbot

Publication date: 12 October 2004

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

Full work available at URL: https://doi.org/10.1016/j.aam.2003.08.006

zbMATH Keywords

NP-complete decision problem\(\#\)-\texttt{MON-2-SAT} problem\#P complete counting

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15)

Cites Work

• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• Counting linear extensions
• The complexity of reconstructing trees from qualitative characters and subtrees
• Phylogenetic supertrees. Combining information to reveal the tree of life
• An efficient algorithm for supertrees
• Reconstruction of rooted trees from subtrees
• The Complexity of Enumeration and Reliability Problems
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions

This page was built for publication: Counting consistent phylogenetic trees is \#P-complete