Sequential Monte Carlo for counting vertex covers in general graphs
DOI10.1007/s11222-015-9546-9zbMath1420.60098OpenAlexW2095363193MaRDI QIDQ294226
Ad Ridder, Zdravko I. Botev, Radislav Vaisman
Publication date: 10 June 2016
Published in: Statistics and Computing (Search for Journal in Brave)
Full work available at URL: https://research.vu.nl/en/publications/bd8d0203-03d1-40b7-b8b0-ac98585aa6f2
dynamic programmingrelaxationrandom graphscounting problemvertex coversequential importance sampling
Computational methods in Markov chains (60J22) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Enumeration in graph theory (05C30) Randomized algorithms (68W20)
Uses Software
Cites Work
- Unnamed Item
- Stochastic enumeration method for counting NP-hard problems
- Efficient Monte Carlo simulation via the generalized splitting method
- The Gibbs cloner for combinatorial optimization, counting and sampling
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Random generation of combinatorial structures from a uniform distribution
- A survey of the theory of hypercube graphs
- Stochastic simulation: Algorithms and analysis
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- On Counting Independent Sets in Sparse Graphs
- Approximate counting by dynamic programming
- Monte-Carlo approximation algorithms for enumeration problems
- The Complexity of Enumeration and Reliability Problems
- Approximately counting cliques
- The Splitting Method for Decision Making
- Reducibility among Combinatorial Problems
- FPTAS for Counting Monotone CNF
- Simulation and the Monte Carlo Method
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
This page was built for publication: Sequential Monte Carlo for counting vertex covers in general graphs
