Minimization of the Number of Edges in an EVMDD by Variable Grouping for Fast Analysis of Multi-State Systems

Author

Nagayama, Shinobu ; Sasao, T. ; Butler, J.T.

Author_Institution

Dept. of Comput. & Network Eng., Hiroshima City Univ., Hiroshima, Japan

fYear

2013

fDate

22-24 May 2013

Firstpage

284

Lastpage

289

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 multi-valued 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.

Keywords

decision diagrams; minimisation; EVMDD; edge-valued multivalued decision diagram; edges number minimization; multistate system; variable grouping; Algorithm design and analysis; Cities and towns; Heuristic algorithms; Merging; Minimization; Optimization; Time complexity; EVMDDs; Minimization algorithm of the number of edges; grouping variables for optimization of decision diagrams; multi-state systems; system analysis based on decision diagrams;

fLanguage

English

Publisher

ieee

Conference_Titel

Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on

Conference_Location

Toyama

ISSN

0195-623X

Print_ISBN

978-1-4673-6067-8

Electronic_ISBN

0195-623X

Type

conf

DOI

10.1109/ISMVL.2013.37

Filename

6524678