A Graph Polynomial for Independent Sets of Bipartite Graphs
From MaRDI portal
Publication:2911069
DOI10.1017/S0963548312000296zbMath1247.05111OpenAlexW2122924340MaRDI QIDQ2911069
Publication date: 12 September 2012
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548312000296
Graph polynomials (05C31) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (3)
Random-cluster dynamics in \(\mathbb {Z}^2\) ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Mixing of Markov chains for independent sets on chordal graphs with bounded separators
Cites Work
- 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
- Fast convergence of the Glauber dynamics for sampling independent sets
- 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
This page was built for publication: A Graph Polynomial for Independent Sets of Bipartite Graphs
