Some disturbing facts about depth-first left-most variable ordering heuristics for binary decision diagrams

A B Rauzy

Journal of Risk and Reliability, 2008, vol. 222, issue 4, 573-582

Abstract: Binary decision diagrams (BDDs) have proven to be a very efficient tool to assess fault trees. However, the size of the BDD, and therefore the efficiency of the whole methodology, is highly dependent on the choice of variable ordering. The determination of the best variable ordering is intractable. Therefore, heuristics have been designed to select reasonably good variable orderings. The most popular of these heuristics consists in numbering variables by means of a depth-first left-most (DFLM) traversal of the formula, after possibly some rearrangements of the inputs of the gates. In this article, this heuristic is studied in a systematic way. It is shown to be very sensitive to the way the formula is written. A series of experiments shows also that the notion of locality of variables, which was believed to be a key issue in the determination of good orderings, must be handled with care. These facts are quite disturbing and raise questions about the design of good variable ordering heuristics.

Keywords: fault trees; binary decision diagrams; variable ordering heuristics (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://journals.sagepub.com/doi/10.1243/1748006XJRR174 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:risrel:v:222:y:2008:i:4:p:573-582

DOI: 10.1243/1748006XJRR174

Access Statistics for this article

More articles in Journal of Risk and Reliability
Bibliographic data for series maintained by SAGE Publications ().