Efficient construction of binary decision diagrams for network reliability with imperfect vertices.

• This paper proposes an algorithm for network reliability with imperfect vertices. • The proposed algorithm constructs a binary decision diagram without creating intermediate representation. • The proposed algorithm runs 50–1000 times faster than existing algorithms for some benchmark networks. This paper discusses evaluation of the network reliability with imperfect vertices, which computes the probability that a subset of nodes is communicable under possible failures of links and nodes. Although the network reliability is efficiently computed utilizing a binary decision diagram (BDD) if assuming link failures only, it can be 10 times slower if considering node failures as well. This is because existing algorithms are designed to repeatedly update a BDD for every node failure in a step-by-step manner. This research proposes an algorithm that creates the final BDD without the redundant repetitions, which greatly improves the computation efficiency. Moreover, this paper presents a better variable order of BDDs among variables corresponding to links and nodes. Under the variable order, the proposed algorithm is compared with existing ones by numerical experiments using various benchmark networks including real communication networks. The results show that the proposed algorithm runs 198.2 times faster than the existing ones for the 10-by-10 grid graph, 1074.6 times faster for the complete graph with 12 vertices, and 65.6 times faster for some well-known benchmark network. For some network instances, the proposed variable order reduces the number of BDD nodes by 15–38% compared with the existing order. This paper reveals that considering imperfect vertices does not impose significant performance overheads. [ABSTRACT FROM AUTHOR]