Rectangular Network Reliability Computation Based on Isomorphism Determination
Yufeng Xiao · Journal of Computers · 2014
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 I.