Counting and sampling SCJ small parsimony solutions

DOI10.1016/j.tcs.2014.07.027zbMath1360.68483OpenAlexW2027203097MaRDI QIDQ740977

István Miklós, Sándor Z. Kiss, Eric Tannier

Publication date: 10 September 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.027

zbMATH Keywords

FPRASnon-approximabilitycounting problemscomputations on discrete structuresFPAUSsingle cut and join

Mathematics Subject Classification ID

Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

The computational complexity of calculating partition functions of optimal medians with Hamming distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the number of double cut-and-join scenarios
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• On the conductance of order Markov chains
• On weighted multiway cuts in trees
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Locating the vertices of a steiner tree in an arbitrary metric space
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Bayesian Phylogenetic Inference from Animal Mitochondrial Genome Arrangements

This page was built for publication: Counting and sampling SCJ small parsimony solutions