Minimization of Average Path Length in BDDs by Variable Reordering

Abstract

Minimizing the Average Path Length (APL) in a BDD reduces the time needed to evaluate Boolean functions represented by BDDs. This paper describes an efficient heuristic APL minimization procedure based on BDD variable reordering. The reordering algorithm is similar to classical variable sifting with the cost function equal to the APL rather than the number of BDD nodes. The main contribution of our paper is a fast way of updating the APL during the swap of two adjacent variables. Experimental results show that the proposed algorithm effectively minimizes the APL of large MCNC benchmark functions, achieving reductions of up to 47%. For some benchmarks, minimizing APL also reduces the BDD node count.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2003
Accession Number
ADA599936

Entities

People

  • Alan Mishchenko
  • Jon T. Butler
  • Shinobu Nagayama
  • Tsutomu Sasao

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computations
  • Computers
  • Information Operations
  • Mathematical Analysis
  • Mathematics
  • Operating Systems
  • Probability
  • Scientific Research
  • Simulations
  • Standards
  • Terminals

Fields of Study

  • Computer science

Readers

  • Computer Engineering
  • Operations Research
  • Rehabilitation and Prosthetic Care for Military Service Members and Veterans with Limb Loss or Disability.