

























Dualization is a key discrete enumeration problem. It is not known whether or not this problem is polynomial-time solvable. Asymptotically optimal dualization algorithms are the fastest among the known dualization algorithms, which is supported by new experiments with various data described in this paper. A theoretical justification of the efficiency of these algorithms on the average was given by E.V. Djukova more than 30 years ago. In this paper, new results on the construction of parallel algorithms for intractable enumeration problems are presented. A new static parallelization scheme for asymptotically optimal dualization algorithms is developed and tested. The scheme is based on statistical estimations of subtasks size.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。