Complexity of Ising Polynomials

DOI10.1017/S0963548312000259zbMath1247.82011arXiv1110.3639MaRDI QIDQ2911072

Tomer Kotek

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

05C31: Graph polynomials

05C10: Planar graphs; geometric and topological aspects of graph theory

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Bipartition polynomials, the Ising model, and domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• The bivariate Ising polynomial of a graph
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Approximating partition functions of the two-state spin system
• Upper bounds to the clique width of graphs
• Computational complexity of counting problems on 3-regular planar graphs
• Approximating clique-width and branch-width
• The complexity of partition functions
• Polynomial-Time Approximation Algorithms for the Ising Model
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• The computational complexity of two‐state spin systems
• On the computational complexity of the Jones and Tutte polynomials
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
• The Computational Complexity of Tutte Invariants for Planar Graphs