Chapter Summary
Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for 20 years, because they efficiently manipulate basic discrete structures such as logic functions and sets of combinations.
Recently, one of the most interesting research topics related to BDDs/ZDDs is the “frontier-based method,” a very efficient algorithm for enumerating and indexing the subsets of a graph that satisfies a given constraint. This work is important because many kinds of practical problems can be efficiently solved by some variations of this algorithm. In this article, we present an overview of the frontier-based method and recent topics on the state-of-the-art algorithms to show the power of enumeration.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Transactions on Computers, Vol. C-35, No. 8, pp. 677–691, 1986. DOI: https://doi.org/10.1109/TC.1986.1676819. 50, 51
Seiji Doi and et al, “Time with class! let’s count!”, 2012. YouTube video, http://www.youtube.com/watch?v=Q4gTV4r0zRs. 57
Hiroshi Imai, Satoru Iwata, Kyoko Sekine, and Kensyu Yoshida, “Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders,” In Jin-Yi Cai and ChakKuen Wong, editors, Computing and Combinatorics, Vol 1090, Lecture Notes in Computer Science, pp. 68–80, Springer Berlin Heidelberg, 1996. 55
Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi, “Distribution loss minimization with guaranteed error bound,” IEEE Transactions on Smart Grid, Vol. 5, No. 1, pp. 102–111, 2014. DOI: https://doi.org/10.1109/TSG.2013.2288976. 56
Takeru Inoue, et al, “Graphillion. http://graphillion.org/”, 2013. 59
Hiroaki Iwashita, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, and Shin-ichi Minato, “Efficient computation of the number of paths in a grid graph with minimal perfect hash functions,” Hokkaido University, Division of Computer Science, TCS Technical Reports, TCSTR- A-10-64, 2013. 57
D. E. Knuth, The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, Vol. 4, fascicle 1. Addison-Wesley, 2009. 50, 52, 53, 55
Shin-ichi Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,” In Proc. of 30th ACM/IEEE Design Automation Conference (DAC’93), pp. 272–277, 1993. DOI: https://doi.org/10.1145/157485.164890. 50, 51, 53
S. Minato, “Recent topics on BDD/ZDD-based discrete structure manipulation,” Proceedings of the 2013 Reed-Muller Workshop (RM-2013), May 24, 2014, Toyama, Japan, pp.1-7. 49
Kyoko Sekine, Hiroshi Imai, and Seiichiro Tani, “Computing the tutte polynomial of a graph of moderate size,” in John Staples, Peter Eades, Naoki Katoh, and Alistair Moffat, editors, Algorithms and Computations, Vol. 1004, Lecture Notes in Computer Science, pp. 224–233. Springer Berlin Heidelberg, 1995. DOI: https://doi.org/10.1007/BFb0015401. 55
N. J. A. Sloane, “The on-line encyclopedia of integer sequences,” http://oeis.org/. DOI: https://doi.org/10.1007/978-3-540-73086-6_12. 57, 58
D. J. A. Welsh, Complexity: Knots, colourings and counting, London Mathematical Society Lecture Note Series, Vol. 186, pp. 372–390, 1993. 55
Rights and permissions
Copyright information
© 2015 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Minato, Si. (2015). The Power of Enumeration–BDD/ZDD-Based Algorithms for Tackling Combinatorial Explosion. In: Applications of Zero-Suppressed Decision Diagrams. Synthesis Lectures on Digital Circuits & Systems. Springer, Cham. https://doi.org/10.1007/978-3-031-79870-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-79870-2_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-79869-6
Online ISBN: 978-3-031-79870-2
eBook Packages: Synthesis Collection of Technology (R0)eBColl Synthesis Collection 6