Complexity and approximability of the cover polynomial
From MaRDI portal
Publication:445242
DOI10.1007/S00037-011-0018-0zbMATH Open1267.68117OpenAlexW2058339257MaRDI QIDQ445242FDOQ445242
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
Recommendations
- Complexity of the Cover Polynomial
- The complexity of the cover polynomials for planar graphs of bounded degree
- Inapproximability of the Tutte polynomial
- The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)
- Inapproximability of the Tutte polynomial of a planar graph
Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of computing the permanent
- The complexity of partition functions
- The Travelling Salesman Problem in Bounded Degree Graphs
- On the computational complexity of the Jones and Tutte polynomials
- Inapproximability of the Tutte polynomial
- On the cover polynomial of a digraph
- Approximate counting, uniform generation and rapidly mixing Markov chains
- NP is as easy as detecting unique solutions
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Approximately Counting Hamilton Paths and Cycles in Dense Graphs
- A Tutte Polynomial for Coloured Graphs
- 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
- A short proof of the rook reciprocity theorem
- Complexity of the Bollobás-Riordan Polynomial
- 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
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- Title not available (Why is that?)
- A Most General Edge Elimination Polynomial
- On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
Cited In (8)
- Cover-Decomposition and Polychromatic Numbers
- Noncommutativity makes determinants hard
- An algorithm of polynomial order for computing the covering dimension of a finite space
- Minimum constellation covers: hardness, approximability and polynomial cases
- Complexity and approximation of the connected set-cover problem
- Title not available (Why is that?)
- Partially Polynomial Kernels for Set Cover and Test Cover
- Polynomial-time algorithms for regular set-covering and threshold synthesis
Uses Software
This page was built for publication: Complexity and approximability of the cover polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445242)
