Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
DOI10.1007/S00224-009-9213-7zbMATH Open1206.68137OpenAlexW2020085754MaRDI QIDQ987376FDOQ987376
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- The Travelling Salesman Problem in Bounded Degree Graphs
- On the computational complexity of the Jones and Tutte polynomials
- 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
- Acyclic orientations of graphs. (Reprint)
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
Cited In (2)
Uses Software
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)
