DocumentCode
3334710
Title
Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems
Author
Minato, Shin-ichi
Author_Institution
NTT LSI Laboratories, Kanagawa Pref., JAPAN
fYear
1993
fDate
14-18 June 1993
Firstpage
272
Lastpage
277
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Design Automation, 1993. 30th Conference on
ISSN
0738-100X
Print_ISBN
0-89791-577-1
Type
conf
DOI
10.1109/DAC.1993.203958
Filename
1600231
Link To Document