The computational complexity of knot and matroid polynomials

DOI10.1016/0012-365X(92)00065-YzbMath0816.57008OpenAlexW2026507889MaRDI QIDQ1313843

Dominic J. A. Welsh

Publication date: 20 July 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(92)00065-y

zbMATH Keywords

matroidsTutte polynomialknot polynomialsIsing partition function\(\#\)P-hard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Relations of low-dimensional topology with graph theory (57M15) Graph theory (05C99)

Related Items

Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Some unitary representations of Thompson's groups \(F\) and \(T\), Computing HOMFLY polynomials of 2-bridge links from 4-plat representation, An algorithm for the Tutte polynomials of graphs of bounded treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tutte polynomials computable in polynomial time
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• A spanning tree expansion of the Jones polynomial
• State models and the Jones polynomial
• Jones polynomials and classical conjectures in knot theory
• On the Kauffman polynomial of an adequate link
• Geometric algorithms and combinatorial optimization
• Some simplified NP-complete graph problems
• On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds
• The Tutte polynomial
• The Tutte Polynomial Part I: General Theory
• A polynomial invariant for knots via von Neumann algebras
• Tutte Polynomials and Link Polynomials
• Tutte Polynomials and Bicycle Dimension of Ternary Matroids
• The Complexity of Enumeration and Reliability Problems
• The computational complexity of matroid properties
• Complexity of Matroid Property Algorithms
• On the computational complexity of the Jones and Tutte polynomials
• Polynomials for Links
• The Computational Complexity of Tutte Invariants for Planar Graphs
• A Decomposition for Combinatorial Geometries
• Knots