Geodesic
On asymptotically optimal enumeration for irreducible coverings of Boolean matrix
Prikladnaâ diskretnaâ matematika, no. 1 (2014), pp. 96-105
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2014},
     number = {1},
     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
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
%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/

[1] Johnson D., Yannakakis M., Papadimitriou C., “On generating all maximal independent sets”, Inform. Process. Lett., 27:3 (1988), 119–123 | DOI | MR | Zbl

[2] Eiter T., Gottlob G., Makino K., “New results on monotone dualization and generating hypergraph transversals”, SIAM J. Comput., 32:2 (2003), 514–537 | DOI | MR | Zbl

[3] Boros E., Elbassioni K., “Generating maximal independent sets for hypergraphs with bounded edge-intersections”, LATIN 2004: Theoretical Informatics, Springer, Berlin–Heidelberg, 2004, 488–498 | DOI | MR | Zbl

[4] Boros E., Gurvich V., Elbassioni K., Khachiyan L., “An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension”, Parallel Process. Lett., 10:4 (2000), 253–266 | DOI | MR

[5] Fredman M. L., Khachiyan L., “On the complexity of dualization of monotone disjunctive normal forms”, J. Algorithms, 21 (1996), 618–628 | DOI | MR | Zbl

[6] Khachiyan L., Boros E., Elbassioni K., Gurvich V., “An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation”, Discr. Appl. Math., 154:16 (2006), 2350–2372 | DOI | MR | Zbl

[7] Dyukova E. V., “Ob asimptoticheski optimalnom algoritme postroeniya tupikovykh testov”, DAN SSSR, 233:4 (1977), 527–530 | MR | Zbl

[8] Dyukova E. V., “O slozhnosti realizatsii diskretnykh (logicheskikh) protsedur raspoznavaniya”, Zhurn. vychisl. matem. i matem. fiziki, 44:3 (2004), 562–572 | MR | Zbl

[9] Dyukova E. V., Inyakin A. S., “Asimptoticheski optimalnoe postroenie tupikovykh pokrytii tselochislennoi matritsy”, Matematicheskie voprosy kibernetiki, 17, 2008, 235–246

[10] Dyukova E. V., Sotnezov R. M., “O slozhnosti zadachi dualizatsii”, Zhurn. vychisl. matem. i matem. fiz., 52:10 (2012), 1926–1935 | MR | Zbl