Power of Enumeration — Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation

Shin-ichi MINATO

doi:10.1587/transinf.2016LOI0002

Open Access
Power of Enumeration — Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation

Shin-ichi MINATO

Full Text Views

99

Cite this

Free PDF (2.3MB)

Summary :

Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for twenty years, because those data structures are useful to 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 Frontier-based search method, a very efficient algorithm for enumerating and indexing the subsets of a graph to satisfy 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 recent research activity related to BDD and ZDD. We first briefly explain the basic techniques for BDD/ZDD manipulation, and then we present several examples of the state-of-the-art algorithms to show the power of enumeration.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.8 pp.1556-1562

Publication Date: 2017/08/01

Publicized: 2017/05/19

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2016LOI0002

Type of Manuscript: Special Section INVITED PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)

Category

Authors

Shin-ichi MINATO
Hokkaido University

Keyword

BDD, ZDD, discrete structure, graph algorithm

Cite this

Copy

Shin-ichi MINATO, "Power of Enumeration — Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 8, pp. 1556-1562, August 2017, doi: 10.1587/transinf.2016LOI0002.
Abstract: Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for twenty years, because those data structures are useful to 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 Frontier-based search method, a very efficient algorithm for enumerating and indexing the subsets of a graph to satisfy 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 recent research activity related to BDD and ZDD. We first briefly explain the basic techniques for BDD/ZDD manipulation, and then we present several examples of the state-of-the-art algorithms to show the power of enumeration.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016LOI0002/_p

Copy

@ARTICLE{e100-d_8_1556,
author={Shin-ichi MINATO, },
journal={IEICE TRANSACTIONS on Information},
title={Power of Enumeration — Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation},
year={2017},
volume={E100-D},
number={8},
pages={1556-1562},
abstract={Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for twenty years, because those data structures are useful to 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 Frontier-based search method, a very efficient algorithm for enumerating and indexing the subsets of a graph to satisfy 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 recent research activity related to BDD and ZDD. We first briefly explain the basic techniques for BDD/ZDD manipulation, and then we present several examples of the state-of-the-art algorithms to show the power of enumeration.},
keywords={},
doi={10.1587/transinf.2016LOI0002},
ISSN={1745-1361},
month={August},}

Copy

TY - JOUR
TI - Power of Enumeration — Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation
T2 - IEICE TRANSACTIONS on Information
SP - 1556
EP - 1562
AU - Shin-ichi MINATO
PY - 2017
DO - 10.1587/transinf.2016LOI0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2017
AB - Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for twenty years, because those data structures are useful to 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 Frontier-based search method, a very efficient algorithm for enumerating and indexing the subsets of a graph to satisfy 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 recent research activity related to BDD and ZDD. We first briefly explain the basic techniques for BDD/ZDD manipulation, and then we present several examples of the state-of-the-art algorithms to show the power of enumeration.
ER -