A memory efficient algorithm for network reliability
We combine the Augmented Ordered Binary Decision Diagram (OBDD-A) with the use of boundary sets to create a method for computing the exact K-terminal or all-terminal reliability of an undirected network with failed edges and perfect vertices. We present the results of implementing this algorithm and...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
IEEE explore
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/27346 |
| _version_ | 1848752238259863552 |
|---|---|
| author | Herrmann, Johannes Soh, Sieteng |
| author2 | na |
| author_facet | na Herrmann, Johannes Soh, Sieteng |
| author_sort | Herrmann, Johannes |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | We combine the Augmented Ordered Binary Decision Diagram (OBDD-A) with the use of boundary sets to create a method for computing the exact K-terminal or all-terminal reliability of an undirected network with failed edges and perfect vertices. We present the results of implementing this algorithm and show that the execution time is comparable with the state of the art and the space requirement is greatly reduced. Indeed the space remains constant when networks increase in size but maintain their structure and maximum boundary set size; with the same amount of memory used for computing a 312 and a 31000 grid network. |
| first_indexed | 2025-11-14T08:05:26Z |
| format | Conference Paper |
| id | curtin-20.500.11937-27346 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:05:26Z |
| publishDate | 2009 |
| publisher | IEEE explore |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-273462017-10-02T02:27:49Z A memory efficient algorithm for network reliability Herrmann, Johannes Soh, Sieteng na binary decision diagram network - reliability K-terminal reliability all-terminal reliability space - efficient. - I boundary set We combine the Augmented Ordered Binary Decision Diagram (OBDD-A) with the use of boundary sets to create a method for computing the exact K-terminal or all-terminal reliability of an undirected network with failed edges and perfect vertices. We present the results of implementing this algorithm and show that the execution time is comparable with the state of the art and the space requirement is greatly reduced. Indeed the space remains constant when networks increase in size but maintain their structure and maximum boundary set size; with the same amount of memory used for computing a 312 and a 31000 grid network. 2009 Conference Paper http://hdl.handle.net/20.500.11937/27346 IEEE explore fulltext |
| spellingShingle | binary decision diagram network - reliability K-terminal reliability all-terminal reliability space - efficient. - I boundary set Herrmann, Johannes Soh, Sieteng A memory efficient algorithm for network reliability |
| title | A memory efficient algorithm for network reliability |
| title_full | A memory efficient algorithm for network reliability |
| title_fullStr | A memory efficient algorithm for network reliability |
| title_full_unstemmed | A memory efficient algorithm for network reliability |
| title_short | A memory efficient algorithm for network reliability |
| title_sort | memory efficient algorithm for network reliability |
| topic | binary decision diagram network - reliability K-terminal reliability all-terminal reliability space - efficient. - I boundary set |
| url | http://hdl.handle.net/20.500.11937/27346 |