HomeIssuesOn asymptotically optimal enumeration for irreducible coverings of Boolean matrix

On asymptotically optimal enumeration for irreducible coverings of Boolean matrix | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 1(23).

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.
Download file
Counter downloads: 69
  • Title On asymptotically optimal enumeration for irreducible coverings of Boolean matrix
  • Headline On asymptotically optimal enumeration for irreducible coverings of Boolean matrix
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(23)
  • Date:
  • DOI
Keywords
булева матрица, перечисление неприводимых покрытий, асимптотически оптимальный алгоритм дуализации, нормальная форма монотонной булевой функции, минимальное вершинное покрытие гиперграфа, Boolean matrix, enumeration of irreducible coverings, asymptotically optimal algorithm for the dualization, CNF and DNF of monotonic Boolean function, minimal transversal of hypergraph
Authors
References
Дюкова Е. В., Сотнезов Р. М. О сложности задачи дуализации // Журн. вычисл. матем. и матем. физ. 2012. Т. 52. №10. С. 1926-1935.
Дюкова Е. В., Инякин А. С. Асимптотически оптимальное построение тупиковых покрытий целочисленной матрицы // Математические вопросы кибернетики. 2008. Т. 17. С. 235-246.
Дюкова Е. В. О сложности реализации дискретных (логических) процедур распознавания // Журн. вычисл. матем. и матем. физики. 2004. Т. 44. №3. С. 562-572.
Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. Т. 233. №4. С. 527-530.
Khachiyan L., Boros E., Elbassioni K., and Gurvich V. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation // Discr. Appl. Math. 2006. V. 154. No. 16. P. 2350-2372. URL: http: //linkinghub.elsevier.com/retrieve/pii/S0166218X06001910.
Fredman M. L. and Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // J. Algorithms. 1996. V.21. P. 618-628.
Boros E., Gurvich V., Elbassioni K., and Khachiyan L. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension // Parallel Process. Lett. 2000. V. 10. No. 4. P. 253-266. URL: http://www.worldscientific.com/doi/ abs/10.1142/S0129626400000251.
Boros E. and Elbassioni K. Generating maximal independent sets for hypergraphs with bounded edge-intersections // LATIN 2004: Theoretical Informatics. Berlin; Heidelberg: Springer, 2004. P. 488-498. URL: http://www.springerlink.com/index/ b9t9wx6ue9t9hvw3.pdf.
Eiter T., Gottlob G., and Makino K. New results on monotone dualization and generating hypergraph transversals // SIAM J. Comput. 2003. V.32. No. 2. P. 514-537.
Johnson D., Yannakakis M., and Papadimitriou C. On generating all maximal independent sets // Inform. Process. Lett. 1988. V.27. No.3. P. 119-123. URL: http://www. sciencedirect.com/science/article/pii/0020019088900658.
On asymptotically optimal enumeration for irreducible coverings of Boolean matrix | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 1(23).
On asymptotically optimal enumeration for irreducible coverings of Boolean matrix | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 1(23).
Download full-text version
Counter downloads: 215
Download file