Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
From MaRDI portal
Publication:987376
DOI10.1007/s00224-009-9213-7zbMath1206.68137OpenAlexW2020085754MaRDI QIDQ987376
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
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- On the algebraic complexity of some families of coloured Tutte polynomials
- Acyclic orientations of graphs. (Reprint)
- PP is as Hard as the Polynomial-Time Hierarchy
- The Travelling Salesman Problem in Bounded Degree Graphs
- A Most General Edge Elimination Polynomial – Thickening of Edges
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Hard Enumeration Problems in Geometry and Combinatorics
- A Tutte Polynomial for Coloured Graphs
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On the computational complexity of the Jones and Tutte polynomials
- A Most General Edge Elimination Polynomial
- Complexity of the Cover Polynomial
