Counting independent sets in graphs with bounded bipartite pathwidth
DOI10.1002/RSA.21003zbMATH Open1522.05202OpenAlexW2903718998MaRDI QIDQ6074656FDOQ6074656
Authors: Martin Dyer, Catherine Greenhill, Haiko Müller 
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
Recommendations
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)
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Graph Classes: A Survey
- Paths, Trees, and Flowers
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Random generation of combinatorial structures from a uniform distribution
- A partial k-arboretum of graphs with bounded treewidth
- The relative complexity of approximate counting problems
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Title not available (Why is that?)
- Characterizations of derived graphs
- Geometric bounds for eigenvalues of Markov chains
- Counting independent sets up to the tree threshold
- On maximal independent sets of vertices in claw-free graphs
- On the numbers of independent \(k\)-sets in a claw free graph
- The roots of the independence polynomial of a clawfree graph
- Approximating the Permanent
- Unimodality, log-concavity, real-rootedness and beyond
- Graph minors. I. Excluding a forest
- Comparison theorems for reversible Markov chains
- The complexity of counting in sparse, regular, and planar graphs
- Shorter Notes: The Roots of a Polynomial Vary Continuously as a Function of the Coefficients
- Reconfiguring independent sets in claw-free graphs
- Title not available (Why is that?)
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- On Markov Chains for Independent Sets
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
- Combinatorics and complexity of partition functions
- Counting independent sets in cocomparability graphs
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Counting matchings of size \(k\) is \#W[1]-hard
- Computing the partition function of a polynomial on the Boolean cube
- Counting independent sets in graphs with bounded bipartite pathwidth
- On the switch Markov chain for perfect matchings
- Computing the independence polynomial: from the tree threshold down to the roots
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)
