This article is cited in 3 papers

Computational Methods in Discrete Mathematics

On asymptotically optimal enumeration for irreducible coverings of Boolean matrix

E. V. Djukova^ab, P. A. Prokofjev<sup>b

a</sup> M. V. Lomonosov Moscow State University, Moscow, Russia
^b Dorodnitsyn Computing Centre of the Russian Academy of Sciences, Moscow, Russia

Abstract: Enumeration problem for irreducible coverings of Boolean matrix is considered. This problem is known as the problem of dualization. Efficiency of dualization algorithm is usually appreciated with the complexity of a step (creating a next irreducible covering). The algorithms being effective in typical case (for almost all matrices of fixed size) are built by using an approach based on the concept of an asymptotically optimal algorithm with a polynomial delay. Two faster modifications of the asymptotically optimal algorithm AO2 are built. Algorithms have been tested on random Boolean matrices.

Keywords: Boolean matrix, enumeration of irreducible coverings, asymptotically optimal algorithm for the dualization, CNF and DNF of monotonic Boolean function, minimal transversal of hypergraph.

UDC: 519.1+519.8