Heuristics to Optimize the Variable Ordering in Binary Decision Diagrams

Download or read book Heuristics to Optimize the Variable Ordering in Binary Decision Diagrams written by Marvin Caspar and published by GRIN Verlag. This book was released on 2021-10-19 with total page 26 pages. Available in PDF, EPUB and Kindle. Book excerpt: Seminar paper from the year 2019 in the subject Computer Science - Commercial Information Technology, grade: 1,0, University of Kaiserslautern, language: English, abstract: In this paper, two fault trees are examined, for which five heuristics are applied to evaluate and compare their effectiveness. The arrangement of variables in a Binary Decision Diagram (BDD) determines the size of the BDD after applying reduction rules and thus plays a decisive role in finding a compact representation of the Boolean function. Since there are already many possible arrangements with only a few variables and techniques for finding the optimal solution requiring too much time, the use of heuristics is needed. The main focus is on known approaches and especially on the dynamic method of the sifting algorithm.