Complexity of the Cover Polynomial
From MaRDI portal
Publication:5428860
DOI10.1007/978-3-540-73420-8_69zbMath1171.05392OpenAlexW1546260663MaRDI QIDQ5428860
Publication date: 28 November 2007
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73420-8_69
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Block interpolation: a framework for tight exponential-time counting complexity ⋮ The drop polynomial of a weighted digraph ⋮ Complexity of the Bollobás-Riordan Polynomial ⋮ Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants ⋮ On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ An extension of the bivariate chromatic polynomial ⋮ Noncommutativity makes determinants hard