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.
Dupuis, P., Kaynar, B., Ridder, A. A. N., Rubinstein, R., & Vaisman, R. (2012). Counting with combined splitting and capture-recapture methods. Stochastic Models, 28(3), 478-502. https://doi.org/10.1080/15326349.2012.699761