IEICE TRANSACTIONS on Information
The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
Summary :
An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.4 pp.271-281
- Publication Date
- 1996/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Seiichiro TANI, Kiyoharu HAMAGUCHI, Shuzo YAJIMA, "The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 4, pp. 271-281, April 1996, doi: .
Abstract: An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_4_271/_p
Copy
@ARTICLE{e79-d_4_271,
author={Seiichiro TANI, Kiyoharu HAMAGUCHI, Shuzo YAJIMA, },
journal={IEICE TRANSACTIONS on Information},
title={The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram},
year={1996},
volume={E79-D},
number={4},
pages={271-281},
abstract={An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
T2 - IEICE TRANSACTIONS on Information
SP - 271
EP - 281
AU - Seiichiro TANI
AU - Kiyoharu HAMAGUCHI
AU - Shuzo YAJIMA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 1996
AB - An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.
ER -
English
