On the computational complexity of the Jones and Tutte polynomials

From MaRDI portal

Publication:4712248

Jump to:navigation, search

DOI10.1017/S0305004100068936zbMath0747.57006WikidataQ55879602 ScholiaQ55879602MaRDI QIDQ4712248

François Jaeger, Dirk Vertigan, Dominic J. A. Welsh

Publication date: 25 June 1992

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

zbMATH Keywords

Alexander-Conway polynomial \(\#P\)-hard computing the Jones polynomial of a link Tutte polynomial of a matroid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Relations of low-dimensional topology with graph theory (57M15)

Related Items

A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings, TOWARDS A QUANTUM ALGORITHM FOR THE PERMANENT, A linear-optical proof that the permanent is # P -hard, COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS, Knots and Graphs: Two Centuries of Interaction, Topological Quantum Computation, A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs, GRAPHICAL CALCULI FOR THE DUBROVNIK POLYNOMIAL WITH APPLICATIONS, A Graph Polynomial for Independent Sets of Bipartite Graphs, Complexity of Ising Polynomials, The Jones polynomials of three-bridge knots via Chebyshev knots and billiard table diagrams, Mixing of the Glauber dynamics for the ferromagnetic Potts model, The Computational Complexity of the Tutte Plane: the Bipartite Case, Unnamed Item, TUTTE POLYNOMIALS OF TENSOR PRODUCTS OF SIGNED GRAPHS AND THEIR APPLICATIONS IN KNOT THEORY, Randomised Approximation in the Tutte Plane, The Complexity of Approximately Counting Tree Homomorphisms, Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, The Markov chain of colourings, Complexity of the Bollobás-Riordan Polynomial, Lifted inference with tree axioms, Topological quantum computation is hyperbolic, Approximating the chromatic polynomial is as hard as computing it exactly, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Computing a link diagram from its exterior, Parameterized Counting and Cayley Graph Expanders, Unnamed Item, The Tutte polynomial of a class of compound graphs and its applications, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Models of random subtrees of a graph, Universality conjectures for activated random walk, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Some Problems on Approximate Counting in Graphs and Matroids, Short certificates for chromatic equivalence, Unnamed Item, Unnamed Item, The BQP-hardness of approximating the Jones polynomial, A DETERMINANT FORMULA FOR THE JONES POLYNOMIAL OF PRETZEL KNOTS, Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices, Verification of the Jones unknot conjecture up to 22 crossings, The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming, Density of Real Zeros of the Tutte Polynomial, Completeness of classical spin models and universal quantum computation, Tutte polynomial of the Apollonian network, Does the Jones Polynomial Detect Unknottedness?, Relative Tutte Polynomials of Tensor Products of Coloured Graphs, A polynomial quantum algorithm for approximating the Jones polynomial, Modifications of Tutte–Grothendieck invariants and Tutte polynomials, ON TANGLES AND MATROIDS, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, P/NP , and the quantum field computer, ARITHMETIC OF POTTS MODEL HYPERSURFACES, Quantum Physics, Topology, Formal Languages, Computation: A Categorical View as Homage to David Hilbert, ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL, ALTERNATING SUM FORMULAE FOR THE DETERMINANT AND OTHER LINK INVARIANTS, ON COMPUTING KAUFFMAN BRACKET POLYNOMIAL OF MONTESINOS LINKS, Why should anyone care about computing with anyons?, Unnamed Item, The HOMFLY-PT polynomial is fixed-parameter tractable, Relative Tutte Polynomials for Coloured Graphs and Virtual Knot Theory, Some Inequalities for Whitney–Tutte Polynomials, The Exponential Time Complexity of Computing the Probability That a Graph Is Connected, A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid, FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES, Quantum algorithms for algebraic problems, Mathematics of topological quantum computing, The computational complexity of knot genus and spanning area, Coefficients and non-triviality of the Jones polynomial, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Exponential growth constants for spanning forests on Archimedean lattices: Values and comparisons of upper bounds, Quantum Computation of Universal Link Invariants, The complexity of approximating the complex-valued Potts model, A BRACKET POLYNOMIAL FOR GRAPHS, I, Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z², The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs, Energy, ropelength, and other physical aspects of equilateral knots., The complexity of approximating the complex-valued Potts model, Computing the Tutte polynomial of Archimedean tilings, The Tutte polynomials of catacondensed benzenoid systems, POST QUANTUM CRYPTOGRAPHY FROM MUTANT PRIME KNOTS, Jones polynomial of knots formed by repeated tangle replacement operations, The random cluster process, The complexities of the coefficients of the Tutte polynomial, Anyonic quantum walks, Block interpolation: a framework for tight exponential-time counting complexity, Transfer-matrix methods meet Ehrhart theory, Relaxations of \(\mathrm{GF}(4)\)-representable matroids, On the evaluation at \((j,j^2)\) of the Tutte polynomial of a ternary matroid, Splitting formulas for Tutte polynomials, Low depth quantum circuits for Ising models, Models of random knots, Edge cut splitting formulas for Tutte-Grothendieck invariants, The drop polynomial of a weighted digraph, On the number of Eulerian orientations of a graph, Inapproximability of the Tutte polynomial of a planar graph, Coupling of quantum angular momenta: an insight into analogic/discrete and local/global models of computation, An atlas of limit set dynamics for asynchronous elementary cellular automata, Tutte polynomial of pseudofractal scale-free web, Holographic algorithms without matchgates, The complexity of approximating complex-valued Ising and Tutte partition functions, Sparse reliable graph backbones, Singularities in Negami's splitting formula for the Tutte polynomial, On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model, The Tutte polynomial of some matroids, Complexity and approximability of the cover polynomial, Upper bound for the number of spanning forests of regular graphs, On the evaluation at \(( - \iota ,\iota )\) of the Tutte polynomial of a binary matroid, The enumeration of vertex induced subgraphs with respect to the number of components, A structured view on weighted counting with relations to counting, quantum computation and applications, The Go polynomials of a graph., Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, The architecture and the Jones polynomial of polyhedral links, Failed disk recovery in double erasure RAID arrays, On the exact evaluation of certain instances of the Potts partition function by quantum computers, Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, Counting polygon triangulations is hard, Some results on generalised Whitney functions, The Tutte polynomial modulo a prime, On the algebraic complexity of some families of coloured Tutte polynomials, Expansions for the Bollobás-Riordan polynomial of separable ribbon graphs, Inapproximability of the Tutte polynomial, A categorification of the Jones polynomial, Knot invariants and the Bollobás-Riordan polynomial of embedded graphs, Computing the Tutte polynomial of lattice path matroids using determinantal circuits, Coloring invariants of knots and links are often intractable, The Potts model and the Tutte polynomial, Interval partitions and activities for the greedoid Tutte polynomial, Tutte polynomials of Fan-like graphs with applications in benzenoid systems, A new invariant of plane bipartite cubic graphs, Braiding, Majorana fermions, Fibonacci particles and topological quantum computing, Plane graphs and link invariants, The Tutte polynomial of a morphism of matroids. IV: Computational complexity, Tutte polynomials computable in polynomial time, Design tools for reporter strands and DNA origami scaffold strands, Computing spin networks, A celtic framework for knots and links, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, On the topology of graph picture spaces, A little statistical mechanics for the graph theorist, On the colored Tutte polynomial of a graph of bounded treewidth, Thomas H. Brylawski (1944--2007), A Tutte-style proof of Brylawski's tensor product formula, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, Interpretations of the Tutte and characteristic polynomials of matroids, A permanent formula for the Jones polynomial, The Tutte-Potts connection in the presence of an external magnetic field, Tutte polynomials of alternating polycyclic chains, Computational complexity and 3-manifolds and zombies, Complexity classes as mathematical axioms, The HOMFLY polynomials of odd polyhedral links, Computing HOMFLY polynomials of 2-bridge links from 4-plat representation, From a zoo to a zoology: Towards a general theory of graph polynomials, Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT, Series-parallel posets and the Tutte polynomial, Fast algorithms for computing Jones polynomials of certain links, Independence polynomials of circulants with an application to music, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, A new algorithm for recognizing the unknot, Bicycle dimension and special points of the Tutte polynomial, Chip firing and all-terminal network reliability bounds, An extension of the bivariate chromatic polynomial, Monomial bases for broken circuit complexes, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, Invariants of composite networks arising as a tensor product, The polytope of win vectors, Combinatorics and topology - François Jaeger's work in knot theory, A weighted graph polynomial from chromatic invariants of knots, The complexity of computing the Tutte polynomial on transversal matroids, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Interpretations of the Tutte polynomials of regular matroids, Forests, colorings and acyclic orientations of the square lattice, The complexity of partition functions, The computational complexity of knot and matroid polynomials, A dichotomy for real weighted Holant problems, On the HOMFLY polynomials of even trigonal bipyramid links

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:4712248&oldid=11991062"