The parametrized complexity of knot polynomials

DOI10.1016/S0022-0000(03)00080-1zbMATH Open1093.68043MaRDI QIDQ1877705FDOQ1877705

Authors: J. P. Mariño, Johann A. Makowsky 

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Recommendations

• The HOMFLY-PT polynomial is fixed-parameter tractable
• On the computational complexity of the Jones and Tutte polynomials
• A polynomial time knot polynomial
• Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• scientific article; zbMATH DE number 1305557

zbMATH Keywords

Jones polynomialsTutte polynomialsHOMFLY polynomialsKauffman polynomials

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• A new polynomial invariant of knots and links
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph minors. XIII: The disjoint paths problem
• Handle-rewriting hypergraph grammars
• Complexity of Finding Embeddings in a k-Tree
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Invariant of Regular Isotopy
• Representation of links by braids: A new algorithm
• Invariants of links of Conway type
• A Tutte polynomial for signed graphs
• Title not available (Why is that?)
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• The computational complexity of knot and link problems
• Knots
• Title not available (Why is that?)
• Classical roots of knot theory
• Title not available (Why is that?)
• Farrell polynomials on graphs of bounded tree width
• Title not available (Why is that?)
• Knots and algebras
• Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Fusion in relational structures and the verification of monadic second-order properties
• COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS
• The fourth Skein Module and the Montesinos-Nakanishi Conjecture for 3-algebraic links
• Calculating the 2-variable polynomial for knots presented as closed braids
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (15)

• Knottedness is in NP, modulo GRH
• Title not available (Why is that?)
• Algorithmic uses of the Feferman-Vaught theorem
• The HOMFLY-PT polynomial is fixed-parameter tractable
• The complexity of lattice knots
• An algorithm to compute the Kauffman polynomial of 2-bridge knots
• On the calculation of the Kauffman bracket polynomial
• Computing HOMFLY polynomials of 2-bridge links from 4-plat representation
• Farrell polynomials on graphs of bounded tree width
• Courcelle's theorem for triangulations
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Planarity of Knots, Register Automata and LogSpace Computability
• Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Title not available (Why is that?)
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width

This page was built for publication: The parametrized complexity of knot polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1877705)