Complexity of the Bollobás-Riordan Polynomial

DOI10.1007/978-3-540-79709-8_12zbMath1143.05023OpenAlexW138003550MaRDI QIDQ3503627

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

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

Related Items

Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Complexity and approximability of the cover polynomial, The enumeration of vertex induced subgraphs with respect to the number of components, An extension of the bivariate chromatic polynomial

Cites Work

• Algorithmic uses of the Feferman-Vaught theorem
• A Tutte polynomial for signed graphs
• From a zoo to a zoology: Towards a general theory of graph polynomials
• On the algebraic complexity of some families of coloured Tutte polynomials
• Acyclic orientations of graphs. (Reprint)
• Hard Enumeration Problems in Geometry and Combinatorics
• A Tutte Polynomial for Coloured Graphs
• On the computational complexity of the Jones and Tutte polynomials
• On the Complexity of the Interlace Polynomial
• Complexity of the Cover Polynomial
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item