A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid
From MaRDI portal
DOI10.1137/110851213zbMath1272.05019arXiv1010.6231OpenAlexW3098327836MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph polynomials (05C31) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Covering Vectors by Spaces: Regular Matroids, A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid, Approximate Counting via Correlation Decay in Spin Systems, On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes), Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inapproximability of the Tutte polynomial
- A decomposition theory for matroids. V: Testing of matrix total unimodularity
- Decomposition of regular matroids
- Splitting formulas for Tutte polynomials
- Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
- Polynomial-Time Approximation Algorithms for the Ising Model
- Approximating the Partition Function of the Ferromagnetic Potts Model
- On the computational complexity of the Jones and Tutte polynomials
- A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid