Zero-suppressed decision diagram
A zero-suppressed decision diagram (ZSDD or ZDD) is a type of binary decision diagram (BDD) where instead of nodes being introduced when the positive and the negative part are different, they are introduced when negative part is different from constant 0. A zero-suppressed decision diagram is also commonly referred to as a zero-suppressed binary decision diagram (ZBDD).
They are useful when dealing with functions that are almost everywhere 0.
In a 2011 talk "All Questions Answered",[1] Donald Knuth referred to ZDD as the most beautiful construct in computer science.
In The Art of Computer Programming, volume 4, Knuth introduces his Simpath algorithm for constructing a ZDD representing all simple paths between two vertices in a graph.
Available packages
- CUDD: A BDD package written in C that implements BDDs and ZBDDs, University of Colorado, Boulder
- JDD, A java library that implements common BDD and ZBDD operations
- Graphillion, A ZDD software implementation based on Python
References
- ^ ""All Questions Answered" by Donald Knuth". YouTube.com. Retrieved 12 June 2013.
- Shin-ichi Minato, "Zero-suppressed BDDs for set manipulation in combinatorial problems", DAC '93: Proceedings of the 30th international conference on Design automation, 1993
- Ch. Meinel, T. Theobald, "Algorithms and Data Structures in VLSI-Design: OBDD – Foundations and Applications", Springer-Verlag, Berlin, Heidelberg, New York, 1998.
External links
- Alan Mishchenko, An Introduction to Zero-Suppressed Binary Decision Diagrams
- Donald Knuth, Fun With Zero-Suppressed Binary Decision Diagrams (ZDDs) (video lecture, 2008)
- Minato Shin-ichi, Counting paths in graphs (fundamentals of ZDD) (video illustration produced on Miraikan)