New insights into breadth-first search edge ordering of regular networks for terminal-pair reliability analysis

Zhusheng Pan, Yuchang Mo, Liudong Xing and Jianmin Han

Journal of Risk and Reliability, 2014, vol. 228, issue 1, 83-92

Abstract: In the binary decision diagram–based terminal-pair network reliability analysis, the size of binary decision diagram heavily depends on the chosen edge ordering. From a theoretical point of view, finding the best ordering is an intractable task. Therefore, heuristics have been used to obtain reasonably good orderings. Among them, the breadth-first search heuristic typically outperforms other heuristics by generating smaller binary decision diagram and thus has been widely used for terminal-pair network reliability analysis. However, the performance of breadth-first search is still only vaguely understood; not much formal work has been done. In this work, we investigate the selection of high-performance root node of breadth-first search ordering for both lattice networks and de Bruijn networks. Empirical study shows that using the two terminal nodes in the terminal-pair network reliability analysis as the root node of the breadth-first search heuristic can have poor performance, and the high-performance root nodes are not randomly distributed. The relationship between the distribution pattern of high-performance root nodes and the rearrangement of successors is also studied. Given that there is often a variation of several orders of magnitude between the sizes of binary decision diagram built using different root nodes for the same network, the application of our results can dramatically reduce the running time and memory usage and make the binary decision diagram–based reliability analysis of large-scale regular networks possible.

Keywords: Network reliability; binary decision diagram; edge ordering heuristic; breadth-first search; lattice network; de Bruijn network (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://journals.sagepub.com/doi/10.1177/1748006X13497706 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:risrel:v:228:y:2014:i:1:p:83-92

DOI: 10.1177/1748006X13497706

Access Statistics for this article

More articles in Journal of Risk and Reliability
Bibliographic data for series maintained by SAGE Publications ().