Title :
EVBDD-based algorithms for integer linear programming, spectral transformation, and function decomposition
Author :
Lai, Yung-Te ; Pedram, Massoud ; Vrudhula, Sarma B K
Author_Institution :
Hitachi Micro Syst. Inc., San Jose, CA, USA
fDate :
8/1/1994 12:00:00 AM
Abstract :
Edge-Valued Binary-Decision Diagrams (EVBDD´s) are directed acyclic graphs that can represent and manipulate integer functions as effectively as Ordered Binary-Decision Diagrams OBDD´s) do for Boolean functions. They have been used in logic verification for showing the equivalence between Boolean functions and arithmetic functions. In this paper, we present EVBDD-based algorithms for solving integer linear programs, computing spectral coefficients of Boolean functions, and performing function decomposition. These algorithms have been implemented in C under the SIS environment and experimental results are provided
Keywords :
Boolean functions; directed graphs; integer programming; linear programming; Boolean functions; C language; EVBDD-based algorithms; SIS environment; directed acyclic graphs; edge-valued binary-decision diagrams; function decomposition; integer functions; integer linear programming; spectral coefficients; Application software; Arithmetic; Boolean functions; Computer applications; Input variables; Integer linear programming; Linear programming; Subspace constraints;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on