Counting with combined splitting and capture-recapture methods

P. Dupuis, B. Kaynar, A.A.N. Ridder, R. Rubinstein, R. Vaisman

Research output: Contribution to JournalArticleAcademicpeer-review


We apply the splitting method to three well-known counting problems, namely 3-SAT, random graphs with prescribed degrees, and binary contingency tables. We present an enhanced version of the splitting method based on the capture-recapture technique, and show by experiments the superiority of this technique for SAT problems in terms of variance of the associated estimators, and speed of the algorithms. © Taylor and Francis Group, LLC.
Original languageEnglish
Pages (from-to)478-502
JournalStochastic Models
Issue number3
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Counting with combined splitting and capture-recapture methods'. Together they form a unique fingerprint.

Cite this