Publication:5891167

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

zbMATH Keywords

Ising modelmatroidsTutte polynomialapproximation algorithms

Mathematics Subject Classification ID

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