Article

Free access

Zero-suppressed BDDs for set manipulation in combinatorial problems

Author:

Shin-ichi MinatoAuthors Info & Claims

DAC '93: Proceedings of the 30th international Design Automation Conference

Pages 272 - 277

https://doi.org/10.1145/157485.164890

Published: 01 July 1993 Publication History

PDF eReader

References

[1]

S. B. Akers: "Binary Decision Diagrams", IEEE Trans. Comput., pp. 509-516, 1978

Google Scholar

[2]

R. E. Bryant: "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Trans. Comput., pp. 677-691 1986

Digital Library

Google Scholar

[3]

M. Fujita, ~I. Fujisawa and n. Kawato: "Evaluation and Improvement of Boolean Comparison Method Based on Binary Decision Diagrams", Proc. IEEE ICCAD'88, pp. 2-5, 1988

Crossref

Google Scholar

[4]

R. K. Gaede,M. R. Mercer, K. M. Bulter and D. E. Ross: "CATAPULT: Concurrent Automatic Testing Allowing Parallelization and Using Limited Topology", Proc. ACM/IEEE 25th DAC, pp. 597- 600, 1988

Digital Library

Google Scholar

[5]

N. Takahashi, n. Ishiura and S. Yajima: "Fault Simulation for Multiple Faults Using Shared BDD Representation of Fault Sets", Proc. IEEE ICCAD'90, pp. 550-553~ 1991

Crossref

Google Scholar

[6]

J. R. Butch, E. M. Clarke, K. L. McMillan and D. L. Dill: "Sequential Circuit Verification Using Symbolic Model Checking", Proc. ACM/IEEE 27th DAC, pp. 46-51, 1990

Digital Library

Google Scholar

[7]

O. Coudert and J. C. Madre: "Implicit and Incremental Computation of Primes and Essential Implicant Primes of Boolean Functions", Proc. ACM/IEEE 29th DAC, pp. 36-39, 1992

Digital Library

Google Scholar

[8]

Bill Lin and Fabio Somenzi: "Minimization of Symbolic Relations", Proc. IEEE ICCAD'90, pp. 88-91, (1990).

Google Scholar

[9]

S. Minato, N. Ishiura and S. Yajima: Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Function Manipulation, ACM/IEEE Proc. 27th DAC, pp. 52-57, 1990

Digital Library

Google Scholar

[10]

M. Fujita, Y. Matsunaga and T. Kakuda: On Variable Ordering of Binary Decision Diagrams for the Application of Multi-level Logic Synthesis, Proc. the European Conference on Design Automation, pp.50- 54, 1991

Digital Library

Google Scholar

[11]

H.-T. Liaw and C.-S. Lin: "On the OBDD- Representation of General Boolean Functions" IEEE Trans. Comput., pp. 661-664, 1992

Digital Library

Google Scholar

[12]

O. Coudert and J. C. Madre: "A New implicit Graph Based Prime and Essential Prime Computation Technique", Proc. International Symposium on Logic Synthesis and Microprocessor Architecture (ISKIT 92, Japan), pp. 125-131, 1992.

Google Scholar

[13]

S. Minato: 'Fast Generation of Irredundant Sumof-Products Forms from Binary Decision Diagrams', Proceedings of the Synthesis and Simulation Meeting and International Interchange (SASIMI'92, Japan), 1992, pp. 64-73

Google Scholar

Cited By

View all

Minato SKawahara JBanbara MHoriyama TTakigawa IYamaguchi Y(2025)Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDsDiscrete Applied Mathematics10.1016/j.dam.2024.10.003360(467-486)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.10.003
Zhong DFang LGuan Q(2024)Dictionary Encoding Based on Tagged Sentential Decision DiagramsAlgorithms10.3390/a1701004217:1(42)Online publication date: 18-Jan-2024
https://doi.org/10.3390/a17010042
NAGAYAMA SSASAO TBUTLER J(2024)Functional Decomposition of Symmetric Multiple-Valued Functions and Their Compact Representation in Decision DiagramsIEICE Transactions on Information and Systems10.1587/transinf.2023LOP0010E107.D:8(922-929)Online publication date: 1-Aug-2024
https://doi.org/10.1587/transinf.2023LOP0010
Show More Cited By

Index Terms

Zero-suppressed BDDs for set manipulation in combinatorial problems

Recommendations

Partially-shared zero-suppressed multi-terminal BDDs: concept, algorithms and applications

Multi-Terminal Binary Decision Diagrams (MTBDDs) are a well accepted technique for the state graph (SG) based quantitative analysis of large and complex systems specified by means of high-level model description techniques. However, this type of ...
Index-Resilient Zero-Suppressed BDDs: Definition and Operations

Zero-Suppressed Binary Decision Diagrams (ZDDs) are widely used data structures for representing and handling combination sets and Boolean functions. In particular, ZDDs are commonly used in CAD for the synthesis and verification of integrated circuits. ...
Efficient Method of Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs
WIRI '05: Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration

Manipulation of large-scale combinatorial data is one of the important fundamental technique for web information retrieval, integration, and mining. In this paper, we propose a new approach based on BDDs (Binary Decision Diagrams) for database analysis ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '93: Proceedings of the 30th international Design Automation Conference

July 1993

768 pages

ISBN:0897915771

DOI:10.1145/157485

Chairman:
Alfred E. Dunlop
AT&T Bell Labs., Murray Hill, NJ

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC93

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC93: The 30th ACM/IEEE Design Automation Conference

June 14 - 18, 1993

Texas, Dallas, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

462
Total Citations
View Citations
2,876
Total Downloads

Downloads (Last 12 months)431
Downloads (Last 6 weeks)49

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Minato SKawahara JBanbara MHoriyama TTakigawa IYamaguchi Y(2025)Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDsDiscrete Applied Mathematics10.1016/j.dam.2024.10.003360(467-486)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.10.003
Zhong DFang LGuan Q(2024)Dictionary Encoding Based on Tagged Sentential Decision DiagramsAlgorithms10.3390/a1701004217:1(42)Online publication date: 18-Jan-2024
https://doi.org/10.3390/a17010042
NAGAYAMA SSASAO TBUTLER J(2024)Functional Decomposition of Symmetric Multiple-Valued Functions and Their Compact Representation in Decision DiagramsIEICE Transactions on Information and Systems10.1587/transinf.2023LOP0010E107.D:8(922-929)Online publication date: 1-Aug-2024
https://doi.org/10.1587/transinf.2023LOP0010
Maekawa YMinakawa TAdachi S(2024)Enumeration-based Crew Rescheduling Support System for Railway Disruption Management列挙アルゴリズムを用いた適応型乗務員運用整理支援システムの開発とその評価IEEJ Transactions on Electronics, Information and Systems10.1541/ieejeiss.144.103144:2(103-109)Online publication date: 1-Feb-2024
https://doi.org/10.1541/ieejeiss.144.103
Sander AFlorea IBurgholzer LWille R(2024)Stripping Quantum Decision Diagrams of their Identity2024 IEEE International Conference on Quantum Software (QSW)10.1109/QSW62656.2024.00032(168-174)Online publication date: 7-Jul-2024
https://doi.org/10.1109/QSW62656.2024.00032
Lim BTan RKawahara JMinato SIkeda K(2024)A Recursive Framework for Evaluating Moments Using Zero-Suppressed Binary Decision DiagramsIEEE Access10.1109/ACCESS.2024.342167612(91886-91895)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3421676
Shindo HPfanschilling VDhami DKersting K(2024)Learning differentiable logic programs for abstract visual reasoningMachine Learning10.1007/s10994-024-06610-2Online publication date: 26-Oct-2024
https://doi.org/10.1007/s10994-024-06610-2
Minato S(2024)Recent Research Activities on Algorithmic Foundations for Social AdvancementWALCOM: Algorithms and Computation10.1007/978-981-97-0566-5_1(1-8)Online publication date: 29-Feb-2024
https://doi.org/10.1007/978-981-97-0566-5_1
Bjørner NNachmanson L(2024)Arithmetic Solving in Z3Computer Aided Verification10.1007/978-3-031-65627-9_2(26-41)Online publication date: 26-Jul-2024
https://doi.org/10.1007/978-3-031-65627-9_2
Husung NDubslaff CHermanns HKöhl M(2024)OxiDDTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-57256-2_13(255-275)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57256-2_13
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Partially-shared zero-suppressed multi-terminal BDDs: concept, algorithms and applications

Index-Resilient Zero-Suppressed BDDs: Definition and Operations

Efficient Method of Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs