Bi-Partition of Shared Binary Decision Diagrams

Abstract

A shared binary decision diagram (SBDD) represents a multiple-output function, where nodes are shared among BDDs representing the various outputs. A partitioned SBDD consists of two or more SBDDs that share nodes. The separate SBDDs are optimized independently, often resulting in a reduction in the number of nodes over a single SBDD. We show a method for partitioning a single SBDD into two parts that reduces the node count. Among the benchmark functions tested, a node reduction of up to 23% is realized.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2002
Accession Number
ADA596368

Entities

People

  • Jon T. Butler
  • Munehiro Matsuura
  • Tsutomu Sasao
  • Yukihiro Iguchi

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computer Science
  • Computers
  • Electronic Mail
  • Electronics
  • Engineering
  • Heuristic Methods
  • Information Operations
  • Nomenclature
  • Schools
  • Simulations
  • Standards
  • Terminals
  • Verification

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.