Information Engineering School, Southwest University of Science and Technology, Mianyang, China; Special Environment Robot Technology Key Laboratory of Sichuan Province, Southwest University of Science and Technology, Mianyang, China

---

Abstract—To decrease repeated computations and improve efficiency, this paper presents a rectangular network reliability computation method based on isomorphism determination. According to the special structure of rectangular network, 2 sorts of subnets are defined for 2×m network, and n sorts of subnets are defined for n×m network. Furthermore, a hash table is designed to record the OBDD (Ordered Binary Decision Diagram) of defined subnet. When the OBDD of a subnet is constructed, if it is the first time to find this subnet and a defined subnet are isomorphic, its OBDD will be recorded in this hash table. Otherwise, there is no need to construct its OBDD and the recorded OBDD can be accessed in above hash table. Thus, the repeated computations from isomorphic subnets can be reduced, and computation costs are saved. Experiment shows this method can efficiently calculate the reliability of rectangular network with large scale.

Index Terms—Network reliability, isomorphic subnet, rectangular network, ordered binary decision diagram.

[PDF]

Cite: Yufeng Xiao, "Rectangular Network Reliability Computation Based on Isomorphism Determination," Journal of Computers vol. 9, no. 11, pp. 2603-2608, 2014.