Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm

Shan Tai Chen, Shun Shii Lin*, Li Te Huang, Chun Jen Wei

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.

Original languageEnglish
Pages (from-to)337-355
Number of pages19
JournalJournal of Heuristics
Issue number3
Publication statusPublished - 2004 May


  • Binary Decision Diagram
  • EBEA
  • Evolutionary algorithm
  • Heuristic algorithm
  • Paralleled algorithm

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm'. Together they form a unique fingerprint.

Cite this