Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-27T09:49:24.283Z Has data issue: false hasContentIssue false
  • English
  • Français

Randomised Approximation in the Tutte Plane

Published online by Cambridge University Press:  12 September 2008

D. J. A. Welsh
D. J. A. Welsh
Affiliation:
Mathematical Institute and Merton College, University of Oxford
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown that unless NP collapses to random polynomial time RP, there can be no fully polynomial randomised approximation scheme for the antiferromagnetic version of the Q-state Potts model.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 1 , March 1994 , pp. 137 - 143
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Phil. Soc. 108, 35–53.Google Scholar
[2]Jerrum, M. and Sinclair, A. (1990) Polynomial-time approximation algorithms for the Ising model (Extended Abstract). Proc. 17th ICALP, Springer-Verlag, 462–475.Google Scholar
[3]Mihail, M. and Winkler, P. (1991) On the number of Eulerian orientations of a graph. Bellcore Technical Memorandum, TM-ARH-018829.Google Scholar
[4]Seymour, P. D. (1981) Nowhere-zero 6-flows. J. Combinatorial Theory (B) 30, 130–135.CrossRefGoogle Scholar
[5]Vertigan, D. L. and Welsh, D. J. A. (1992) The computational complexity of the Tutte plane: the bipartite case. Combinatorics, Probability and Computing 1, 181–187.Google Scholar
[6]Welsh, D. J. A. (1993) Complexity: Knots Colourings and Counting. London Mathematical Society Lecture Note Series 186, Cambridge University Press.Google Scholar