Sequential Monte Carlo for counting vertex covers in general graphs

DOI10.1007/s11222-015-9546-9zbMath1420.60098MaRDI 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

zbMATH Keywords

dynamic programming; relaxation; random graphs; counting problem; vertex cover; sequential importance sampling

Mathematics Subject Classification ID

60J22: Computational methods in Markov chains

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

05C30: Enumeration in graph theory

68W20: Randomized algorithms

Uses Software

• Chaff

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