Asymptotically optimal dualization algorithms

DOI10.1134/S0965542515050103zbMath1326.90049MaRDI QIDQ2354515

P. A. Prokofjev, E. V. Dyukova

Publication date: 13 July 2015

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

dualizationBoolean matrixasymptotically optimal algorithmirreducible coveringenumeration with a polynomial-time delay

Mathematics Subject Classification ID

Boolean programming (90C09)

Related Items (5)

Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions ⋮ Logical correctors in the problem of classification by precedents ⋮ Dualization problem over the product of chains: asymptotic estimates for the number of solutions ⋮ On the logical analysis of partially ordered data in the supervised classification problem ⋮ Finding maximal independent elements of products of partial orders (the case of chains)

Uses Software

• UCI-ml

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of discrete generation problems
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• On generating all maximal independent sets
• Efficient algorithms for dualizing large-scale hypergraphs
• On the complexity of the dualization problem
• The complexity of the realization of certain recognition procedures
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• LATIN 2004: Theoretical Informatics
• Discrete analysis of feature descriptions in recognition problems of high dimensionality

This page was built for publication: Asymptotically optimal dualization algorithms