A Novel Convolution-Based Algorithm for the Acyclic Network Symbolic Reliability Function Problem

Abstract

Acyclic (binary-state) networks are commonly implemented in many diverse disciplines and applications, including information systems, processes management, project management. These networks owe their popularity to the fact that they do not use directed cycles. Network reliability is the most commonly used tool for evaluating and managing systems modeled on acyclic networks, and minimal paths (MPs) play a significant role in evaluating this reliability. This study therefore proposes a new algorithm based on a novel convolution concept for evaluating acyclic network reliability. The proposed algorithm is able to find all convolution-based MP sets within polynomial time, and then obtain the symbolic function of the acyclic network reliability in terms of those convolution-based MP sets based on the pivotal decomposition. Its total time complexity is $O(2^{n})$ , which is the best among all existing MP algorithms which are at least $O(2^{\vert P\vert })$ , where $O(\vert P\vert) = O(2^{n})$ , and $n$ and $\vert P\vert $ are the number of nodes and MPs, respectively. The correctness and time complexity of the proposed algorithm is proven and examined. An example is used to display the novel convolution-based algorithm is implemented to solve the acyclic network reliability problem.

Keywords

• Network reliability
• acyclic network
• minimal path (MP)
• convolution
• the pivotal decomposition