A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid

DOI10.1137/110851213zbMath1272.05019arXiv1010.6231MaRDI QIDQ5891167

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 25 September 2013

Published in: SIAM Journal on Computing, Automata, Languages and Programming (Search for Journal in Brave)

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

zbMATH Keywords

Ising model; matroids; Tutte polynomial; approximation algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

05C31: Graph polynomials

68R10: Graph theory (including graph drawing) in computer science

05B35: Combinatorial aspects of matroids and geometric lattices

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms