A Graph Polynomial for Independent Sets of Bipartite Graphs

DOI10.1017/S0963548312000296zbMath1247.05111OpenAlexW2122924340MaRDI QIDQ2911069

Qi Ge, Daniel Štefanković

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

zbMATH Keywords

matchingsgraph polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Graph Polynomial for Independent Sets of Bipartite Graphs