Sequential Monte Carlo for counting vertex covers in general graphs

DOI10.1007/S11222-015-9546-9zbMATH Open1420.60098OpenAlexW2095363193MaRDI QIDQ294226FDOQ294226

Authors: Radislav Vaisman, Z. I. Botev, A. Ridder 

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

Recommendations

• A Sequential Importance Sampling Algorithm for Counting Linear Extensions
• scientific article; zbMATH DE number 861427
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• scientific article; zbMATH DE number 1962833
• Stochastic enumeration method for counting NP-hard problems

zbMATH Keywords

dynamic programmingsequential importance samplingrandom graphsrelaxationvertex covercounting problem

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Dynamic programming (90C39) Enumeration in graph theory (05C30)

Cites Work

• Stochastic simulation: Algorithms and analysis
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Reducibility among combinatorial problems
• Simulation and the Monte Carlo Method
• Random generation of combinatorial structures from a uniform distribution
• Random graphs.
• The Complexity of Enumeration and Reliability Problems
• A survey of the theory of hypercube graphs
• Monte-Carlo approximation algorithms for enumeration problems
• The Gibbs cloner for combinatorial optimization, counting and sampling
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• The complexity of counting in sparse, regular, and planar graphs
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• On Counting Independent Sets in Sparse Graphs
• Stochastic enumeration method for counting NP-hard problems
• Approximate counting by dynamic programming
• Approximately counting cliques
• The splitting method for decision making
• FPTAS for counting monotone CNF
• 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
• Efficient Monte Carlo simulation via the generalized splitting method

Cited In (3)

• Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation
• A Sequential Importance Sampling Algorithm for Counting Linear Extensions
• Organization mechanism and counting algorithm on vertex-cover solutions

Uses Software

• Chaff

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294226)