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

DOI10.1007/S00224-009-9213-7zbMATH Open1206.68137OpenAlexW2020085754MaRDI QIDQ987376FDOQ987376

Authors: Markus Bläser, Holger Dell, Johann A. Makowsky Error creating thumbnail:

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

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

zbMATH Keywords

computational complexityTutte polynomialgraph polynomialsalgebraic reductions

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The Travelling Salesman Problem in Bounded Degree Graphs
• On the computational complexity of the Jones and Tutte polynomials
• Title not available (Why is that?)
• A Tutte polynomial for signed graphs
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• PP is as Hard as the Polynomial-Time Hierarchy
• From a zoo to a zoology: Towards a general theory of graph polynomials
• A Tutte Polynomial for Coloured Graphs
• Algorithmic uses of the Feferman-Vaught theorem
• On the algebraic complexity of some families of coloured Tutte polynomials
• A most general edge elimination polynomial -- thickening of edges
• Hard Enumeration Problems in Geometry and Combinatorics
• A Most General Edge Elimination Polynomial
• Complexity of the Cover Polynomial
• Inapproximability of the Tutte polynomial
• Acyclic orientations of graphs. (Reprint)
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)

Cited In (4)

• Complexity of the Bollobás-Riordan Polynomial
• Boshernitzan’s condition, factor complexity, and an application
• A most general edge elimination polynomial -- thickening of edges
• On the complexity of generalized chromatic polynomials

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)