Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/87255
Authors: 
Vaisman, Radislav
Botev, Zdravko
Ridder, Ad
Year of Publication: 
2013
Series/Report no.: 
Tinbergen Institute Discussion Paper 13-122/III
Abstract: 
In this paper we describe a Sequential Importance Sampling (SIS) procedure for counting the number of vertex covers in general graphs. The performance of SIS depends heavily on how close the SIS proposal distribution is to a uniform one over a suitably restricted set. The proposed algorithm introduces a probabilistic relaxation technique that uses Dynamic Programming in order to efficiently estimate this uniform distribution. The numerical experiments show that the scheme compares favorably with other existing methods. In particular the method is compared with cachet - an exact model counter, and the state of the art SampleSearch, which is based on Belief Networks and importance sampling.
Subjects: 
Vertex Cover
Counting problem
Sequential importance sampling
Dynamic Programming
Relaxation
Random Graphs
JEL: 
C61
C63
Document Type: 
Working Paper

Files in This Item:
File
Size
200.19 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.