Counting independent sets in graphs with bounded bipartite pathwidth
From MaRDI portal
Publication:6074656
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)
Recommendations
Cites work
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- 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
- 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 Cuts and of Computing the Probability that a Graph is Connected
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- 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
(7)- Computing \(k\)-independent sets for regular bipartite graphs
- The Complexity of Finding Paths in Graphs with Bounded Independence Number
- Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
- Counting independent sets in graphs with bounded bipartite pathwidth
- Approximately counting independent sets in bipartite graphs via graph containers
- A graph polynomial for independent sets of bipartite graphs
- Counting weighted independent sets beyond the permanent
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)
