Name
Abstract | ||
|---|---|---|
Modern exact methods solving the NP-hard k-terminal reliability problem are based on Binary Decision Diagrams (BDDs). The system redundancy structure represented by the input graph is converted into a BDD whose size highly depends on the predetermined variable ordering. As finding the optimal available ordering has exponential complexity, a heuristic must be used. Currently, the breadth-first-search is considered to be state-of-the-art. Based on Hardy's decomposition approach, we derive a novel static heuristic which yields significantly smaller BDD sizes for a wide variety of network structures, especially irregular ones. As a result, runtime and memory requirements can be drastically reduced for BDD-based reliability methods. Applying the decomposition method with the new heuristic to three medium-sized irregular networks from the literature, an average speedup of around 9,400 is gained and the memory consumption drops to less than 0.1 percent. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/DSN.2014.55 | DSN |
Keywords | Field | DocType |
optimisation,hardy decomposition approach,input graph,binary decision diagrams,tree searching,k-terminal reliability,breadth-first-search,bdd, decomposition, k-terminal reliability, dependability analysis,np-hard k-terminal reliability,bdd-based k-terminal reliability,novel variable ordering heuristic,dependability analysis,decomposition,reliability,bdd,graph theory,network theory (graphs),breadth first search,boolean functions,vectors,sorting,data structures | Boolean function,Data structure,Heuristic,Computer science,Algorithm,Binary decision diagram,Decomposition method (constraint satisfaction),Sorting,Redundancy (engineering),Speedup | Conference |
ISSN | Citations | PageRank |
1530-0889 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minh Lê | 1 | 8 | 2.29 |
| Josef Weidendorfer | 2 | 115 | 17.98 |
| Max Walter | 3 | 54 | 9.17 |