Title :
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
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;
Conference_Titel :
Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on
Conference_Location :
Toyama
Print_ISBN :
978-1-4673-6067-8
Electronic_ISBN :
0195-623X
DOI :
10.1109/ISMVL.2013.37
