Counting independent sets in graphs with bounded bipartite pathwidth
From MaRDI portal
(Redirected from Publication:6074656)
Counting independent sets in graphs with bounded bipartite pathwidth (scientific article; zbMATH DE number 7749486)
Counting independent sets in graphs with bounded bipartite pathwidth (scientific article; zbMATH DE number 7749486)
Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)
Recommendations
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Approximating the Permanent
- Characterizations of derived graphs
- Combinatorics and complexity of partition functions
- Comparison theorems for reversible Markov chains
- Computing the independence polynomial: from the tree threshold down to the roots
- Computing the partition function of a polynomial on the Boolean cube
- Counting independent sets in cocomparability graphs
- Counting independent sets in graphs with bounded bipartite pathwidth
- Counting independent sets up to the tree threshold
- Counting matchings of size \(k\) is \#W[1]-hard
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Geometric bounds for eigenvalues of Markov chains
- Graph Classes: A Survey
- Graph minors. I. Excluding a forest
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- On Markov Chains for Independent Sets
- On maximal independent sets of vertices in claw-free graphs
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
- On the numbers of independent k-sets in a claw free graph
- On the switch Markov chain for perfect matchings
- Paths, Trees, and Flowers
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Random generation of combinatorial structures from a uniform distribution
- Reconfiguring independent sets in claw-free graphs
- Shorter Notes: The Roots of a Polynomial Vary Continuously as a Function of the Coefficients
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The complexity of counting in sparse, regular, and planar graphs
- The relative complexity of approximate counting problems
- The roots of the independence polynomial of a clawfree graph
- Unimodality, log-concavity, real-rootedness and beyond
Cited in
(8)- Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
- Counting independent sets in graphs with bounded bipartite pathwidth
- Computing \(k\)-independent sets for regular bipartite graphs
- A graph polynomial for independent sets of bipartite graphs
- Counting weighted independent sets beyond the permanent
- The Complexity of Finding Paths in Graphs with Bounded Independence Number
- Approximately counting independent sets in bipartite graphs via graph containers
- Thick forests
This page was built for publication: Counting independent sets in graphs with bounded bipartite pathwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074656)
