On the computational complexity of the Jones and Tutte polynomials

François Jaeger, Dirk Vertigan, Dominic Welsh

Type: Article

Publication Date: 1990-07-01

Citations: 485

DOI: https://doi.org/10.1017/s0305004100068936

View Publication

Locations

Mathematical Proceedings of the Cambridge Philosophical Society - View

Similar Works

Action	Title	Year	Authors
+	The computational complexity of knot and matroid polynomials	1994	Dominic Welsh
+	The complexities of the coefficients of the Tutte polynomial	1995	J. D. Annan
+	The Computational Complexity of the Tutte Plane: the Bipartite Case	1992	Dirk Vertigan Dominic Welsh
+	ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL	2010	H. Ahmadi Paweł Wocjan
+ PDF Chat	Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width	1998	Steven D. Noble
+	The Tutte polynomial of a ported matroid	1989	Seth Chaiken
+	Matroids and the Tutte polynomial	2018	Scott Corry David Perkinson
+	On the evaluation at (3, 3) of the Tutte polynomial of a graph	1988	Michel Las Vergnas
+ PDF Chat	Randomised Approximation Schemes for Tutte-Gröthendieck Invariants	1995	Dominic Welsh
+ PDF Chat	Combinatorics of the Tutte polynomial and planar maps	2014	Julien Courtiel
+	The Tutte Polynomial for Matroids of Bounded Branch-Width	2006	Petr Hliněný
+	On Tutte polynomials and cycles of plane graphs	1988	François Jaeger
+	The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid	2020	Andreas Björklund Petteri Kaski
+	Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials	2012	Leslie Ann Goldberg Mark Jerrum
+	Computing the Tutte Polynomial with Restricted “Width”	2005	Petr Hliněný Omer Giménez Marc Noy
+ PDF Chat	Inapproximability of the Tutte polynomial of a planar graph	2012	Leslie Ann Goldberg Mark Jerrum
+	The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid	2020	Andreas Björklund Petteri Kaski
+	Extremal graphs for the Tutte polynomial	2021	Nathan Kahl
+	A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth	2023	Isja Mannens Jesper Nederlof
+ PDF Chat	A Characterization of the Tutte Polynomial via Combinatorial Embeddings	2008	Olivier Bernardi

Works That Cite This (401)

Action	Title	Year	Authors
+	A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs	2008	Michel Las Vergnas
+ PDF Chat	Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP	2018	Cornelius Brand Holger Dell Marc Roth
+	Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials	2012	Leslie Ann Goldberg Mark Jerrum
+	The Complexity of Ferromagnetic Ising with Local Fields	2006	ESLIE ANN GOLDBERG Mark Jerrum
+	Symmetries in proteins: A knot theory approach	1996	Shi‐Jie Chen Ken A. Dill
+	Complexity Dichotomies for Counting Problems	2017	Jin‐Yi Cai Xi Chen
+	The Complexity of Partition Functions on Hermitian Matrices	2010	Marc Thurley
+	The Computational Complexity of the Tutte Plane: the Bipartite Case	1992	Dirk Vertigan Dominic Welsh
+	Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case	1995	Noga Alon Alan Frieze Dominic Welsh
+	Quantum automata, braid group and link polynomials	2006	Silvano Garnerone Annalisa Marzuoli Mario Rasetti

Works Cited by This (25)

Action	Title	Year	Authors
+	Le Polynôme De Martin D'un Graphe Eulerien	1983	Michel Las Vergnas
+ PDF Chat	Two-dimensional monomer-dimer systems are computationally intractable	1990	Mark Jerrum
+ PDF Chat	Tutte polynomials and bicycle dimension of ternary matroids	1989	François Jaeger
+	On the Kauffman polynomial of an adequate link	1988	Morwen Thistlethwaite
+ PDF Chat	A decomposition for combinatorial geometries	1972	Thomas Brylawski
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+	On Tutte polynomials and cycles of plane graphs	1988	François Jaeger
+	On the Dimer Solution of Planar Ising Models	1966	Michael E. Fisher
+	Convexity in oriented matroids	1980	Michel Las Vergnas
+	Facing up to arrangements: face-count formulas for partitions of space by hyperplanes	1975	Thomas Zasĺavsky