Complexity and approximability of the cover polynomial

DOI10.1007/s00037-011-0018-0zbMath1267.68117OpenAlexW2058339257MaRDI QIDQ445242

Mahmoud Fouz, Holger Dell, Markus Bläser

Publication date: 24 August 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0018-0

zbMATH Keywords

approximation Tutte polynomial permanent counting complexity graph polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Noncommutativity makes determinants hard

Uses Software

tutte_bhkk

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
The complexity of computing the permanent
Inapproximability of the Tutte polynomial
From a zoo to a zoology: Towards a general theory of graph polynomials
NP is as easy as detecting unique solutions
Approximate counting, uniform generation and rapidly mixing Markov chains
On the algebraic complexity of some families of coloured Tutte polynomials
An algorithm for the Tutte polynomials of graphs of bounded treewidth
The cycle-path indicator polynomial of a digraph
On the cover polynomial of a digraph
A short proof of the rook reciprocity theorem
The complexity of partition functions
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Complexity of the Bollobás-Riordan Polynomial
The Travelling Salesman Problem in Bounded Degree Graphs
A Most General Edge Elimination Polynomial – Thickening of Edges
On Counting Homomorphisms to Directed Acyclic Graphs
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
Hard Enumeration Problems in Geometry and Combinatorics
Approximately Counting Hamilton Paths and Cycles in Dense Graphs
Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
A Tutte Polynomial for Coloured Graphs
On the computational complexity of the Jones and Tutte polynomials
A Most General Edge Elimination Polynomial
On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Complexity and approximability of the cover polynomial