Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
type: Item
instance of: scholarly article
title: Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
zbMATH Open document ID: 1206.68137
author: Markus Bläser
author: Holger Dell
author: Johann A. Makowsky
published in: Theory of Computing Systems
publication date: 2010-08-13T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5770222
zbMATH Keywords: computational complexity
zbMATH Keywords: Tutte polynomial
zbMATH Keywords: graph polynomials
zbMATH Keywords: algebraic reductions
describes a project that uses: tutte_bhkk
MaRDI profile type: Publication
full work available at URL: s00224-009-9213-7
OpenAlex ID: W2020085754
cites work: A Most General Edge Elimination Polynomial
cites work: The Travelling Salesman Problem in Bounded Degree Graphs
cites work: Complexity of the Cover Polynomial
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: Q4398864
cites work: A Tutte Polynomial for Coloured Graphs
cites work: Exponential Time Complexity of the Permanent and the Tutte Polynomial
cites work: Q5313291
cites work: Q3549645
cites work: A Most General Edge Elimination Polynomial – Thickening of Edges
cites work: On the computational complexity of the Jones and Tutte polynomials
cites work: A Tutte polynomial for signed graphs
cites work: Hard Enumeration Problems in Geometry and Combinatorics
cites work: On the algebraic complexity of some families of coloured Tutte polynomials
cites work: Algorithmic uses of the Feferman-Vaught theorem
cites work: From a zoo to a zoology: Towards a general theory of graph polynomials
cites work: Q3416249
cites work: Acyclic orientations of graphs. (Reprint)
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: Q4111952
DOI: 10.1007/S00224-009-9213-7
description: scientific article; zbMATH DE number 5770222