Monte-Carlo algorithms for enumeration and reliability problems
Monte-Carlo algorithms for enumeration and reliability problems
复制标题
DOI：
10.1109/sfcs.1983.35
复制
发表时间：
1983-11
期刊：
影响因子：
--
通讯作者：
R. Karp;M. Luby
中科院分区：
文献类型：
--
作者：
R. Karp;M. Luby
1. 引言
我们提出一种简单但非常通用的蒙特卡罗技术，用于枚举和可靠性问题的近似求解。给出了若干应用，包括：
1. 估计具有给定顶点数的三角化平面地图的数量；
2. 估计一组集合的并集的基数；
3. 估计一个以析取范式表示的布尔函数的输入组合的数量
1. Introduction We present a simple but very general Monte-Carlo technique for the approximate solution of enumeration and reliability problems. Several applications are given, including: 1. Estimating the number of triangulated plane maps with a given number of ver-tices; 2. Estimating the cardinality of a union of sets; 3. Estimating the number of input combinations for which a boolean function, presented in disjunctive normal form,