A Graph Polynomial for Independent Sets of Bipartite Graphs
From MaRDI portal
Publication:2911069
DOI10.1017/S0963548312000296zbMath1247.05111MaRDI QIDQ2911069
Publication date: 12 September 2012
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
05C31: Graph polynomials
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Random-cluster dynamics in \(\mathbb {Z}^2\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A two-variable interlace polynomial
- Fast evaluation of interlace polynomials on graphs of bounded treewidth
- An approximation trichotomy for Boolean \#CSP
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Random generation of combinatorial structures from a uniform distribution
- Prime divisors of the Lagarias sequence
- The relative complexity of approximate counting problems
- Computational complexity of counting problems on 3-regular planar graphs
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Counting independent sets up to the tree threshold
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Graph Polynomials and Their Applications I: The Tutte Polynomial
- Graph Polynomials and Their Applications II: Interrelations and Interpretations
- Polynomial-Time Approximation Algorithms for the Ising Model
- On Counting Independent Sets in Sparse Graphs
- The Complexity of Ferromagnetic Ising with Local Fields
- Dynamic Matrix Rank
- The computational complexity of two‐state spin systems
- On the computational complexity of the Jones and Tutte polynomials
- On Markov Chains for Independent Sets
- A Contribution to the Theory of Chromatic Polynomials
- A two-variable Artin conjecture
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
