The parametrized complexity of knot polynomials

DOI10.1016/S0022-0000(03)00080-1zbMath1093.68043MaRDI QIDQ1877705

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)

zbMATH Keywords

Tutte polynomialsJones polynomialsHOMFLY polynomialsKauffman polynomials

Mathematics Subject Classification ID

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

Related Items

Courcelle's theorem for triangulations, Algorithmic uses of the Feferman-Vaught theorem, Farrell polynomials on graphs of bounded tree width, On the calculation of the Kauffman bracket polynomial, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, The HOMFLY-PT polynomial is fixed-parameter tractable, Computing HOMFLY polynomials of 2-bridge links from 4-plat representation, From a zoo to a zoology: Towards a general theory of graph polynomials

Cites Work

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