A graph polynomial for independent sets of bipartite graphs

DOI10.1017/S0963548312000296MaRDI QIDQ2911069zbMATH OpenOpenAlexFDO

Authors Q. Ge, D. Š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)

Recommendations

• A graph polynomial for independent sets of bipartite graphs
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• On the Complexity of the Interlace Polynomial

Cites work

• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 50132 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A two-variable Artin conjecture
• A two-variable interlace polynomial
• An approximation trichotomy for Boolean \#CSP
• Computational complexity of counting problems on 3-regular planar graphs
• Counting independent sets up to the tree threshold
• Dynamic Matrix Rank
• Fast convergence of the Glauber dynamics for sampling independent sets
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph polynomials and their applications. I: The Tutte polynomial
• Graph polynomials and their applications. II: Interrelations and interpretations
• On Counting Independent Sets in Sparse Graphs
• On Markov Chains for Independent Sets
• On the computational complexity of the Jones and Tutte polynomials
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Polynomial-Time Approximation Algorithms for the Ising Model
• Prime divisors of the Lagarias sequence
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Ferromagnetic Ising with Local Fields
• The complexity of counting in sparse, regular, and planar graphs
• The computational complexity of two‐state spin systems
• The relative complexity of approximate counting problems

Cited in

(11)

• Random-cluster dynamics in \(\mathbb {Z}^2\)
• Mixing of Markov chains for independent sets on chordal graphs with bounded separators
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
• Bipartite graphs as polynomials and polynomials as bipartite graphs
• An algorithm for calculating the independence and vertex-cover polynomials of a graph
• On the independence polynomial of an antiregular graph
• A graph polynomial for independent sets of bipartite graphs
• Julia set of some graphs using independence polynomials
• A graph polynomial arising from community structure (extended abstract)
• A polynomial Turing-kernel for weighted independent set in bull-free graphs

This page was built for publication: A graph polynomial for independent sets of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911069)