Abstract | ||
---|---|---|
In the optimization of decision diagrams, variable reordering approaches are often used to minimize the number of nodes. However, such approaches are less effective for analysis of multi-state systems given by monotone structure functions. Thus, in this paper, we propose algorithms to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. The proposed algorithms minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multi-valued variables, we can reduce the number of nodes as well. To show the effectiveness of the proposed algorithms, we compare the proposed algorithms with conventional optimization algorithms based on a variable reordering approach. Experimental results show that the proposed algorithms reduce the number of edges by up to 15% and the number of nodes by up to 47%, compared to the conventional ones. This results in a speed-up of the analysis of multi-state systems by about three times. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1587/transinf.2013LOP0011 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
minimization algorithm of the number of edges, EVMDDs, grouping variables for optimization of decision diagrams, multi-state systems, system analysis using decision diagrams | Mathematical optimization,Pattern recognition,Computer science,Algorithm,Influence diagram,Optimization algorithm,Artificial intelligence,Structure function,Monotone polygon | Journal |
Volume | Issue | ISSN |
E97D | 9 | 1745-1361 |
Citations | PageRank | References |
2 | 0.39 | 16 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shinobu Nagayama | 1 | 218 | 25.30 |
Tsutomu Sasao | 2 | 1083 | 141.62 |
Jon T. Butler | 3 | 321 | 42.77 |
Mitchell A. Thornton | 4 | 280 | 40.94 |
Theodore W. Manikas | 5 | 55 | 7.75 |