Complexity of graph polynomials

MaRDI QIDQ3447288zbMATH OpenFDO

Authors Steven D. Noble

Publication date 28 June 2007

zbMATH Keywords

graph polynomials

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• The computational complexity of knot and matroid polynomials
• The exact complexity of the Tutte polynomial
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Tutte polynomials computable in polynomial time
• The Computational Complexity of Tutte Invariants for Planar Graphs

Cited in

(20)

• The computational complexity of knot and matroid polynomials
• The complexities of the coefficients of the Tutte polynomial
• Splitting formulas for Tutte polynomials
• The Tutte polynomial of some matroids
• The complexity of the cover polynomials for planar graphs of bounded degree
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• Complexity of the Bollobás-Riordan Polynomial
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs
• Evaluations of Graph Polynomials
• Complexity of the Cover Polynomial
• Evaluating the Rank Generating Function of a Graphic 2-Polymatroid
• The exact complexity of the Tutte polynomial
• Logical Approaches to Computational Barriers
• On the complexity of generalized chromatic polynomials
• Dominic Welsh: his work and influence
• Tutte polynomials computable in polynomial time
• Graph compression and the zeros of polynomials
• Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions

This page was built for publication: Complexity of graph polynomials

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