The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 1996-04-25
著者
-
Hamaguchi Kiyoharu
Department Of Bioinformatic Engineering Guraduate School Of Information Science And Technology Osaka
-
Hamaguchi Kiyoharu
Department Of Information Science Kyoto University
-
Yajima Shuzo
Department Of Information Science Kyoto University
-
Tani S
Ntt Corp. Yokosuka‐shi Jpn
-
TANI Seiichiro
Department of Information Science, The University of Tokyo
-
Yajima Shuzo
Department Of Information Science Facu1ty Of Engineering Kyoto University
関連論文
- Verifying Signal-Transition Consistency of High-Level Designs Based on Symbolic Simulation(Special Issue on Test and Verification of VLSI)
- A Computer Communication Control Technique for Virtualization of Network Memory Resources and Its Implementation
- A Partially Explicit Method for Efficient Symbolic Checking of Language Containment (Special Section on VLSI Design and CAD Algorithms)
- Regular Temporal Logic Expressively Equivalent to Finite Automata and Its Application to Logic Design Verification
- Locally Exhaustive Testing of Combinational Circuits Using Linear Logic Circuits
- Minimum One-Shot State Assignment for Asynchronous Sequential Machines Using BDD
- On the Power of Non-deterministic Quantum Finite Automata(Special Issue on Selected Papers from LA Symposium)
- An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division (Special Section on Discrete Mathematics and Its Applications)
- The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
- A Raster-scan Computer Graphic Display Device Having Random-scan Functions with Color Specifying Light Pen Facility
- Combinatorial Algorithms Using Boolean Processing
- Minimum Single Transition-Time Assignments for Asynchronous Sequential Circuits Using BDD