Abstract:
The design of efficient on average algorithms for discrete enumeration problems is studied. The dualization problem, which is a central enumeration problem, is considered. New asymptotically optimal dualization algorithms are constructed. It is shown that they are superior in time costs to earlier constructed asymptotically optimal dualization algorithms and other available dualization algorithms with different design features.
Key words:dualization, Boolean matrix, asymptotically optimal algorithm, irreducible covering, enumeration with a polynomial-time delay.
Fulltext:
PDF file (238 kB)