A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid
From MaRDI portal
Publication:5891167
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
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
Related Items
Covering Vectors by Spaces: Regular Matroids, On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes), 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, 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