DocumentCode
2237471
Title
On solving covering problems [logic synthesis]
Author
Coudert, Olivier
Author_Institution
Synopsys Inc., Mountain View, CA, USA
fYear
1996
fDate
3-7 Jun, 1996
Firstpage
197
Lastpage
202
Abstract
The set covering problem and the minimum cost assignment problem (respectively known as unate and binate covering problem) arise throughout the logic synthesis flow. This paper investigates the complexity and approximation ratio of two lower bound computation algorithms from both a theoretical and practical point of view. It also presents a new pruning technique that takes advantage of the partitioning
Keywords
computational complexity; logic design; logic partitioning; approximation ratio; complexity; logic synthesis flow; lower bound computation algorithms; minimum cost assignment problem; partitioning; pruning technique; set covering problem; Boolean functions; Cost function; Design automation; Heuristic algorithms; Logic; Minimization; Permission;
fLanguage
English
Publisher
ieee
Conference_Titel
Design Automation Conference Proceedings 1996, 33rd
Conference_Location
Las Vegas, NV
ISSN
0738-100X
Print_ISBN
0-7803-3294-6
Type
conf
DOI
10.1109/DAC.1996.545572
Filename
545572
Link To Document