Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra

References

• Asmussen S, Glynn PW (2007) Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability, Vol. 57 (Springer-Verlag, New York).Crossref, Google Scholar
• Blanchet J, Rudoy D (2009) Rare event simulation and counting problems. Rubino G, Tuffin B, eds. Rare Event Simulation Using Monte Carlo Methods, 1st ed. (Wiley, New York), 171–192.Crossref, Google Scholar
• Blitzstein J, Diaconis P (2010) A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Math. 6(4):489–522.Crossref, Google Scholar
• Bollobás B (2001) Random Graphs. Cambridge Studies in Advanced Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Botev Z, Kroese D (2012) Efficient Monte Carlo simulation via the generalized splitting method. Statist. Comput. 22(1):1–16.Crossref, Google Scholar
• Chen Y, Diaconis P, Holmes SP, Liu JS (2005) Sequential Monte Carlo methods for statistical analysis of tables. J. Amer. Statist. Assoc. 100(469):109–120.Crossref, Google Scholar
• Cook JL, Ramirez-Marquez JE (2007) Two-terminal reliability analyses for a mobile ad hoc wireless network. Reliability Engrg. System Safety 92(6):821–829.Crossref, Google Scholar
• Dyer M (2003) Approximate counting by dynamic programming. Proc. 35th ACM Sympos. Theory Comput. (ACM, New York), 693–699.Crossref, Google Scholar
• Dyer M, Frieze A, Jerrum M (1999) On counting independent sets in sparse graphs. 40th Annual Sympos. Foundations Comput. Sci., New York, 210–217.Crossref, Google Scholar
• Gertsbakh I, Shpungin Y (2009) Models of Network Reliability: Analysis, Combinatorics, and Monte Carlo, 1st ed. (CRC Press, Boca Raton, FL).Google Scholar
• Gertsbakh I, Shpungin Y (2011) Network Reliability and Resilience. SpringerBriefs in Electrical and Computer Engineering (Springer, Berlin).Crossref, Google Scholar
• Gogate V, Dechter R (2006) A new algorithm for sampling CSP solutions uniformly at random. Principles and Practice of Constraint Programming, LNCS 4204 (Springer, New York), 711–715.Crossref, Google Scholar
• Gogate V, Dechter R (2007) Approximate counting by sampling the backtrack-free search space. Proc. 22nd National Conf. Artificial Intelligence, Vol. 1 (AAAI Press, Palo Alto, CA),198–203.Google Scholar
• Gomes CP, Sabharwal A, Selman B (2009) Model counting. Biere A, Heule M, van Maaren H, Walsh T, eds. Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, Vol. 185 (IOS Press, Amsterdam), 633–654.Google Scholar
• Günneç D, Salman S (2011) Assessing the reliability and the expected performance of a network under disaster risk. OR Spectrum 33(3):499–523.Crossref, Google Scholar
• Heidelberger P (1995) Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simulation 5(1):43–85.Crossref, Google Scholar
• Jerrum M, Sinclair A (1997) The Markov chain Monte Carlo method: An approach to approximate counting and integration. Hochbaum DS, ed., Approximation Algorithms for NP-hard Problems (PWS Publishing, Boston), 482–520.Google Scholar
• Jerrum M, Sinclair A, Vigoda E (2004) A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51(4):671–697.Crossref, Google Scholar
• Jerrum MR, Valiant LG, Vazirani VV (1986) Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43(2–3):169–188.Crossref, Google Scholar
• Karp RM, Luby M (1983) Monte-Carlo algorithms for enumeration and reliability problems. Proc. 24th Annual Sympos. Foundations Comput. Sci. SFCS ’83 (IEEE Computer Society, Washington, DC), 56–64 .Crossref, Google Scholar
• Kroese DP, Taimre T, Botev ZI (2011) Handbook of Monte Carlo Methods (John Wiley and Sons, New York).Crossref, Google Scholar
• Lin L, Gen M (2006) A self-controlled genetic algorithm for reliable communication network design. IEEE Congress Evolutionary Comput., Vancouver, 640–647.Crossref, Google Scholar
• Marseguerra M, Zio E, Podofillini L, Coit D (2005) Optimal design of reliable network systems in presence of uncertainty. IEEE Trans. Reliability 54(2):243–253.Crossref, Google Scholar
• Moskewicz MW, Madigan CF, Zhao Y, Zhang L, Malik S (2001) Chaff: Engineering an efficient SAT solver. Proc. 38th Annual Design Automation Conf. (ACM, New York), 530–535.Crossref, Google Scholar
• Rasmussen LE (1997) Approximately counting cliques. Random Structures & Algorithms 11(4):395–411.Crossref, Google Scholar
• Rubino G, Tuffin B (2009) Rare Event Simulation Using Monte Carlo Methods (Wiley, New York).Crossref, Google Scholar
• Rubinstein R (2009) The Gibbs cloner for combinatorial optimization, counting and sampling. Methodology Comput. Appl. Probab. 11(2):491–549.Crossref, Google Scholar
• Rubinstein R (2012) Stochastic enumeration method for counting NP-hard problems. Methodology Comput. Appl. Probab. 15(2):249–291.Crossref, Google Scholar
• Rubinstein R, Kroese D (2007) Simulation and the Monte Carlo Method, 2nd ed. (John Wiley and Sons, New York).Crossref, Google Scholar
• Rubinstein R, Ad R, Radislav V (2013) Fast Sequential Monte Carlo Methods for Counting and Optimization (John Wiley and Sons, New York).Crossref, Google Scholar
• Rubinstein R, Dolgin A, Vaisman R (2012) The splitting method for decision making. Comm. Statist. Simulation Comput. 41(6):905–921.Crossref, Google Scholar
• Sang T, Bacchus F, Beame P, Kautz HA, Pitassi T (2004) Combining component caching and clause learning for effective model counting. Seventh Internat. Conf. Theory Appl. Satisfiability Testing, Vancouver.Google Scholar
• Vadhan SP (1997) The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2):398–427.Crossref, Google Scholar
• Vaisman R (2013) Stochastic enumeration methods for counting, rare-events and optimization. Unpublished Ph.D. thesis, Technion, Israel Institute of Technology, Technion, Haifa, Israel.Google Scholar
• Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3):410–421.Crossref, Google Scholar
• Wei W, Selman B (2005) A new approach to model counting. Bacchus F, Walsh T, eds. Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science, Vol. 3569 (Springer, Berlin), 324–339.Crossref, Google Scholar