New ideas for solving covering problems

Authors:

Abstract
Covering problems occur at several steps during logic synthesisincluding two-level minimization and DAG covering.This paper presents a better lower bound computationalgorithm and two new pruning techniques thatsignificantly improve the efficiency of covering problemsolvers. We show that these techniques reduce by up tothree orders of magnitude the time required to solve coveringproblems exactly.1 IntroductionThe (unate or binate) covering problem is a well knownintractable problem....