EXPLICIT AND IMPLICIT ALGORITHMS FOR BINATE COVERING PROBLEMS

We survey techniques for solving binate covering problems, an optimiza tion step often occurring in logic synthesis applications, Standard ex act solutions are found with a branch-and-bound exhaustive search, mad e more efficient by bounding away regions of the search space. Standar d approaches are said to be explicit because they work on a direct rep resentation of the binate table, usually as a matrix, Recently, coveri ng problems involving large tables have been attacked with implicit te chniques, They are based on the representation by reduced-ordered bina ry decision diagrams of an encoding of the binate table, We show how t able reductions, computation of a lower bound, and of a branching colu mn can be performed on the table so represented, We report experiments for two different applications that demonstrate that implicit techniq ues handle instances beyond the reach of explicit techniques, Various aspects of our original research are presented for the first time, tog ether with a selection of the most important old and new results scatt ered in many sources.