Counting independent sets in graphs with bounded bipartite pathwidth
From MaRDI portal
Publication:6074656
DOI10.1002/rsa.21003zbMath1522.05202OpenAlexW2903718998MaRDI QIDQ6074656
Catherine Greenhill, Haiko Müller, Martin Dyer
Publication date: 12 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://eprints.whiterose.ac.uk/174580/1/1812.03195v4.pdf
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorics and complexity of partition functions
- Geometric bounds for eigenvalues of Markov chains
- The roots of the independence polynomial of a clawfree graph
- Graph minors. I. Excluding a forest
- Random generation of combinatorial structures from a uniform distribution
- On maximal independent sets of vertices in claw-free graphs
- A partial k-arboretum of graphs with bounded treewidth
- Comparison theorems for reversible Markov chains
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- Counting independent sets in cocomparability graphs
- On the numbers of independent \(k\)-sets in a claw free graph
- The relative complexity of approximate counting problems
- Counting independent sets in graphs with bounded bipartite pathwidth
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Counting independent sets up to the tree threshold
- Unimodality, log-concavity, real-rootedness and beyond
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Reconfiguring Independent Sets in Claw-Free Graphs
- Approximating the Permanent
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
- Shorter Notes: The Roots of a Polynomial Vary Continuously as a Function of the Coefficients
- Graph Classes: A Survey
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
- Computing the Partition Function of a Polynomial on the Boolean Cube
- Computing the Independence Polynomial: from the Tree Threshold down to the Roots
- On the Switch Markov Chain for Perfect Matchings
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- On Markov Chains for Independent Sets
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Paths, Trees, and Flowers
- Characterizations of derived graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
