Complexity and approximability of the cover polynomial
From MaRDI portal
Publication:445242
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
Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Uses Software
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
