Title :
Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems
Author :
Minato, Shin-ichi
Author_Institution :
NTT LSI Laboratories, Kanagawa Pref., JAPAN
Abstract :
In this paper, we propose Zero-Suppressed BDDs (0-Sup-BDDs), which are BDDs based on a new reduction rule. This data structure brings unique and compact representation of sets which appear in many combinatorial problems. Using 0-Sup-BDDs, we can manipulate such sets more simply and efficiently than using original BDDs. We show the properties of 0-Sup-BDDs, their manipulation algorithms, and good applications for LSI CAD systems.
Keywords :
Algorithm design and analysis; Application software; Binary decision diagrams; Binary trees; Boolean functions; Circuit faults; Data structures; Design automation; Laboratories; Large scale integration;
Conference_Titel :
Design Automation, 1993. 30th Conference on
Print_ISBN :
0-89791-577-1
DOI :
10.1109/DAC.1993.203958
