Minimization of the Number of Edges in an EVMDD by Variable Grouping for Fast Analysis of Multi-State Systems
Abstract
This paper proposes an algorithm to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. We minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multivalued variables, we can also reduce the number of nodes. However, minimization of the number of nodes by grouping variables is not always effective for fast analysis of multi-state systems. On the other hand, minimization of the number of edges is effective. Experimental results show that the proposed algorithm for minimizing the number of edges reduces the number of edges by up to 15% and the number of nodes by up to 47%. This results in a speed-up of the analysis of multi-state systems by about three times.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2013
- Accession Number
- ADA590017
Entities
People
- Jon T. Butler
- Shinobu Nagayama
- Tsutomu Sasao
Organizations
- Naval Postgraduate School