On the Complexity of the Interlace Polynomial
From MaRDI portal
Publication:4910711
DOI10.4230/LIPIcs.STACS.2008.1337zbMath1259.68076arXiv0707.4565MaRDI QIDQ4910711
Christian Hoffmann, Markus Bläser
Publication date: 19 March 2013
Full work available at URL: https://arxiv.org/abs/0707.4565
computational complexityapproximationgraph transformationinterlace polynomialindependent set polynomial
Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (8)
Complexity of the Bollobás-Riordan Polynomial ⋮ Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ An extension of the bivariate chromatic polynomial
This page was built for publication: On the Complexity of the Interlace Polynomial
