Title of article
Efficient dualization of O(log n)-term monotone disjunctive normal
Author/Authors
Kazuhisa Makino، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2003
Pages
8
From page
305
To page
312
Abstract
This paper shows that O(log n)-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.
Keywords
Hypergraph , Polynomial total time algorithm , Transversal computation , Monotone Boolean function , Dualization , k-term DNF , Combinatorial enumeration
Journal title
Discrete Applied Mathematics
Serial Year
2003
Journal title
Discrete Applied Mathematics
Record number
885519
Link To Document