Show simple item record

dc.contributor.authorHerrmann, Johannes
dc.contributor.authorSoh, Sieteng
dc.identifier.citationHerrmann, Johannes and Soh, Sieteng. 2009. A memory efficient algorithm for network reliability, APCC 2009, Oct 8 2009, pp. 703-707. Shanghai, China: IEEE explore.

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.

dc.publisherIEEE explore
dc.subjectbinary decision diagram
dc.subjectnetwork - reliability
dc.subjectK-terminal reliability
dc.subjectall-terminal reliability
dc.subjectspace - efficient. - I
dc.subjectboundary set
dc.titleA memory efficient algorithm for network reliability
dc.typeConference Paper
dcterms.source.titleProceeding of the 15th Asia-Pacific conference on communications APCC 2009
dcterms.source.seriesProceeding of the 15th Asia-Pacific conference on communications APCC 2009
dcterms.source.conferenceAPCC 2009
dcterms.source.conference-start-dateOct 8 2009
curtin.accessStatusOpen access
curtin.facultySchool of Science and Computing
curtin.facultyDepartment of Computing
curtin.facultyFaculty of Science and Engineering

Files in this item


This item appears in the following Collection(s)

Show simple item record