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

DOI10.1016/j.aam.2018.09.002zbMath1486.68081arXiv1506.06107OpenAlexW2963719403WikidataQ129208656 ScholiaQ129208656MaRDI QIDQ1631451

István Miklós, Heather C. Smith

Publication date: 6 December 2018

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

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

zbMATH Keywords

computational complexitypartition functionmediangenome rearrangementFPRASFPAUSsingle cut-or-join

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Counting and sampling SCJ small parsimony solutions
• Random generation of combinatorial structures from a uniform distribution
• On the conductance of order Markov chains
• Counting linear extensions
• On weighted multiway cuts in trees
• Locating the vertices of a steiner tree in an arbitrary metric space
• Computational Complexity of Probabilistic Turing Machines
• Equation of State Calculations by Fast Computing Machines
• The complexity of theorem-proving procedures