Complexity of the Bollobás-Riordan Polynomial

DOI10.1007/978-3-540-79709-8_12MaRDI QIDQ3503627zbMATH OpenOpenAlexFDO

Authors Markus Bläser, Holger Dell, Johann A. Makowsky

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79709-8_12

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Relations of low-dimensional topology with graph theory (57M15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
• On the algebraic complexity of some families of coloured Tutte polynomials
• Complexity of graph polynomials
• The computational complexity of knot and matroid polynomials
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

Cites work

• A Tutte Polynomial for Coloured Graphs
• A Tutte polynomial for signed graphs
• Acyclic orientations of graphs. (Reprint)
• Algorithmic uses of the Feferman-Vaught theorem
• Complexity of the Cover Polynomial
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Hard Enumeration Problems in Geometry and Combinatorics
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• Inapproximability of the Tutte polynomial
• On the algebraic complexity of some families of coloured Tutte polynomials
• On the Complexity of the Interlace Polynomial
• On the computational complexity of the Jones and Tutte polynomials
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

Cited in

(8)

• An extension of the bivariate chromatic polynomial
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• A most general edge elimination polynomial -- thickening of edges
• Complexity and approximability of the cover polynomial
• Boshernitzan’s condition, factor complexity, and an application
• The enumeration of vertex induced subgraphs with respect to the number of components
• My writing
• Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions

This page was built for publication: Complexity of the Bollobás-Riordan Polynomial

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