Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions

DOI10.1007/S00224-009-9213-7MaRDI QIDQ987376zbMATH OpenOpenAlexFDO

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

Publication date 13 August 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9213-7

zbMATH Keywords

algebraic reductionscomputational complexitygraph polynomialsTutte polynomial

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Complexity of the Bollobás-Riordan Polynomial
• 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 Most General Edge Elimination Polynomial
• A most general edge elimination polynomial -- thickening of edges
• 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 AND REAL COMPUTATION: A MANIFESTO
• Complexity of the Cover Polynomial
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• 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 1179517 (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 computational complexity of the Jones and Tutte polynomials
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• PP is as Hard as the Polynomial-Time Hierarchy
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The Travelling Salesman Problem in Bounded Degree Graphs

Cited in

(9)

• Complexity of the Bollobás-Riordan Polynomial
• A most general edge elimination polynomial -- thickening of edges
• Boshernitzan’s condition, factor complexity, and an application
• On the complexity of generalized chromatic polynomials
• Meta-theorems for graph polynomials
• The complexity of the greedoid Tutte polynomial
• My writing
• On the counting complexity of the cover polynomial for simple graphs
• Graph polynomials: some questions on the edge

Describes a project that uses

Uses Software

• tutte_bhkk

This page was built for publication: Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions

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