The parametrized complexity of knot polynomials

DOI10.1016/S0022-0000(03)00080-1MaRDI QIDQ1877705zbMATHFDO

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)

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)

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

Cites work

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

Cited in

(15)

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

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)