Randomised Approximation in the Tutte Plane

DOI10.1017/S0963548300001036zbMath0811.68105OpenAlexW2004492294MaRDI QIDQ4306438

Dominic J. A. Welsh

Publication date: 1 May 1995

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

Full work available at URL: https://doi.org/10.1017/s0963548300001036

zbMATH Keywords

Potts modelTutte polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Related Items

Unnamed Item ⋮ A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs ⋮ On the algebraic complexity of some families of coloured Tutte polynomials ⋮ Inapproximability of the Tutte polynomial ⋮ The Potts model and the Tutte polynomial

Cites Work

• Nowhere-zero 6-flows
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• On the computational complexity of the Jones and Tutte polynomials