Geodesic
On asymptotically optimal enumeration for irreducible coverings of Boolean matrix
Prikladnaâ diskretnaâ matematika, no. 1 (2014), pp. 96-105

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : Boolean matrix
Keywords: enumeration of irreducible coverings, asymptotically optimal algorithm for the dualization, CNF and DNF of monotonic Boolean function, minimal transversal of hypergraph. 
@article{PDM_2014_1_a10,
     author = {E. V. Djukova and P. A. Prokofjev},
     title = {On asymptotically optimal enumeration for irreducible coverings of {Boolean} matrix},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {96--105},
     publisher = {mathdoc},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_1_a10/}
}
TY  - JOUR
AU  - E. V. Djukova
AU  - P. A. Prokofjev
TI  - On asymptotically optimal enumeration for irreducible coverings of Boolean matrix
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 96
EP  - 105
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_1_a10/
LA  - ru
ID  - PDM_2014_1_a10
ER  - 
%0 Journal Article
%A E. V. Djukova
%A P. A. Prokofjev
%T On asymptotically optimal enumeration for irreducible coverings of Boolean matrix
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 96-105
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_1_a10/
%G ru
%F PDM_2014_1_a10
E. V. Djukova; P. A. Prokofjev. On asymptotically optimal enumeration for irreducible coverings of Boolean matrix. Prikladnaâ diskretnaâ matematika, no. 1 (2014), pp. 96-105. http://geodesic.mathdoc.fr/item/PDM_2014_1_a10/