Efficient dualization of -term monotone disjunctive normal forms ?
This paper shows that -term monotone disjunctive normal forms (DNFs) ? can be dualized in incremental polynomial time, where n is the number of variables in ?. This improves upon the trivial result that k-term monotone DNFs can be dualized in polynomial time, where k is bounded by some constant.
dualization monotone boolean function k-term dnf hypergraph transversal computation combinatorial enumeration polynomial total time algorithm