Complexity and approximability of the cover polynomial
type: Item
instance of: scholarly article
title: Complexity and approximability of the cover polynomial
zbMATH Open document ID: 1267.68117
author: Markus Bläser
author: Holger Dell
author: Mahmoud Fouz
published in: Computational Complexity
publication date: 2012-08-24T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C31
zbMATH DE Number: 6072038
zbMATH Keywords: graph polynomial
zbMATH Keywords: counting complexity
zbMATH Keywords: approximation
zbMATH Keywords: permanent
zbMATH Keywords: Tutte polynomial
describes a project that uses: tutte_bhkk
MaRDI profile type: Publication
full work available at URL: s00037-011-0018-0
OpenAlex ID: W2058339257
cites work: An algorithm for the Tutte polynomials of graphs of bounded treewidth
cites work: A Most General Edge Elimination Polynomial
cites work: The Travelling Salesman Problem in Bounded Degree Graphs
cites work: Complexity of the Bollobás-Riordan Polynomial
cites work: Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
cites work: Q4789190
cites work: A Tutte Polynomial for Coloured Graphs
cites work: The complexity of partition functions
cites work: A short proof of the rook reciprocity theorem
cites work: On the cover polynomial of a digraph
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: The cycle-path indicator polynomial of a digraph
cites work: Approximately Counting Hamilton Paths and Cycles in Dense Graphs
cites work: On Counting Homomorphisms to Directed Acyclic Graphs
cites work: Q4198056
cites work: On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
cites work: Inapproximability of the Tutte polynomial
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: Approximate counting, uniform generation and rapidly mixing Markov chains
cites work: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
cites work: Hard Enumeration Problems in Geometry and Combinatorics
cites work: On the algebraic complexity of some families of coloured Tutte polynomials
cites work: From a zoo to a zoology: Towards a general theory of graph polynomials
cites work: Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
cites work: Q4298260
cites work: The complexity of computing the permanent
cites work: NP is as easy as detecting unique solutions
DOI: 10.1007/S00037-011-0018-0
description: scientific article; zbMATH DE number 6072038