Counting Weighted Independent Sets beyond the Permanent
DOI10.1137/20M1347747zbMath1467.05124arXiv1909.03414MaRDI QIDQ4997141
Haiko Müller, Kristina Vušković, Martin Dyer, Mark R. Jerrum
Publication date: 28 June 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.03414
decomposition; counting; randomized algorithm; independent set; claw-free graph; FPRAS; fully polynomial randomized approximation scheme; fork-free graph
68Q25: Analysis of algorithms and problem complexity
05C30: Enumeration in graph theory
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W20: Randomized algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of the algorithmic aspects of modular decomposition
- The complexity of computing the permanent
- On minimal prime extensions of a four-vertex graph in a prime graph
- The strong perfect graph theorem
- The roots of the independence polynomial of a clawfree graph
- Decomposition by clique separators
- Random generation of combinatorial structures from a uniform distribution
- Recognizing claw-free perfect graphs
- On maximal independent sets of vertices in claw-free graphs
- Geometric algorithms and combinatorial optimization
- A description of claw-free perfect graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The relative complexity of approximate counting problems
- Claw-free graphs. VII. Quasi-line graphs
- An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
- On counting perfect matchings in general graphs
- Counting independent sets in graphs with bounded bipartite pathwidth
- Recognizing Berge graphs
- Graph Theory
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Approximating the Permanent
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Line perfect graphs
- Graph Classes: A Survey
- Paths, Trees, and Flowers
- The Structure of Claw‐Free Perfect Graphs
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
- Transitiv orientierbare Graphen
- Characterizations of derived graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
