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

zbMATH Keywords

dynamic programmingrelaxationrandom graphscounting problemvertex coversequential importance sampling

Mathematics Subject Classification ID

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

• 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

This page was built for publication: Sequential Monte Carlo for counting vertex covers in general graphs