Name
Abstract | ||
|---|---|---|
The terminal-pair reliability problem, i.e. the problem of determining the probability that there exists at least one path of working edges connecting the terminal nodes, is known to be NP-hard. Thus, bounding algorithms are used to cope with large graph sizes. However, they still have huge demands in terms of memory. We propose a memory-efficient implementation of an extension of the Gobien-Dotson bounding algorithm. Without increasing runtime, compression of relevant data structures allows us to use low-bandwidth high-capacity storage. In this way, available hard disk space becomes the limiting factor. Depending on the input structures, graphs with several hundreds of edges (i.e. system components) can be handled. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.entcs.2012.11.015 | Electr. Notes Theor. Comput. Sci. |
Keywords | Field | DocType |
memory-efficient implementation,relevant data structure,low-bandwidth high-capacity storage,huge demand,two-terminal reliability problem,large graph size,terminal node,memory-efficient bounding algorithm,available hard disk space,input structure,system component,terminal-pair reliability problem,factoring | Bounding volume hierarchy,Data structure,Graph,Existential quantification,Computer science,Limiting factor,Algorithm,Theoretical computer science,Bounding interval hierarchy,Bounding overwatch | Journal |
Volume | ISSN | Citations |
291, | 1571-0661 | 2 |
PageRank | References | Authors |
0.38 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minh Lê | 1 | 8 | 2.29 |
| Max Walter | 2 | 54 | 9.17 |
| Josef Weidendorfer | 3 | 115 | 17.98 |