Adv Syst Sci Appl 2019; 01; 1-11 Published online at https://ijassa.ipu.ru/index.php/ijassa/article/view/656 A simple improved algorithm to find all the lower boundary points in a multiple-node-pair multistate flow network Majid Forghani-elahabad1*, Nelson Kagan2 1) Centro de Matemática, Computação e Cognição – CMCC, Universidade Federal do ABC – UFABC, Santo André, SP, Brazil E-mail: majid@usp.br 2) Department of Electrical Engineering, University of Sao Paulo, Sao Paulo, Brazil E-mail: nelsonk@pea.usp.br Received October 17, 2018; Revised February 20, 2019; Published April 10, 2019 Abstract: There are several real-world systems which can be modeled as multistate flow networks (MFNs). Many researchers have worked on reliability evaluation of an MFN, and accordingly variety of approaches have been proposed in this regard. The problem of finding all the lower boundary points (LBPs) in a multistate flow network (MFN) has been attracting significant attention in the recent decades as these vectors can be used for reliability evaluation of MFNs. Once all the LBPs are determined, the reliability of the network can be calculated by using some techniques such as the inclusion–exclusion principle or the sum of disjoint products (SDP). Several algorithms have been proposed to address this problem in the literature in terms of minimal paths or minimal cuts. As in the real systems the data (flow or commodity) are usually transmitting from several sources to a number of destinations, the problem of determining all the LBPs in a multi-node-pair MFN is considered in this work. An improved algorithm is proposed to address the problem. The algorithm is illustrated through a benchmark network example. The complexity results are computed. The efficiency of the algorithm is demonstrated through a numerical example and the complexity results. Keywords: Lower boundary points; Multi-node-pair multistate flow network; minimal paths; d- MP problem; System reliability; Sum of disjoint product. 1. INTRODUCTION Due to ever-increasing importance of transport networks such as communication or telecommunication networks, there is certainly need for designing and constructing the most possible reliable systems. A transport network can be generally modeled as a multistate flow network (MFN, also called stochastic-flow network) whose arcs (and possibly nodes) have randomly variable capacities due to failures, the need for maintenance, operations activities, etc. [1-22]. Traditionally, several indices have been proposed and employed to measure the reliability of an MFN in the literature. The most attractive reliability index is the two- terminal reliability (TTR) or the source-destination reliability index [2-4, 14]. For a given demand value of d, the TTR in an MFN is the probability of transmitting at least d units of flow (data or commodity) from a source node to a destination node [5-9]. However, the realistic networks such as communication or telecommunication networks need to transmit concurrently several demands of signals (flow or data) from various source nodes to a number of destination nodes, and consequently the problem of reliability evaluation of multi- node-pair MFN (MNP-MFN) has been emerged [5, 8, 14, 16]. In an MNP-MFN, there is a * Corresponding author: Email address: majid@usp.br, Phone: +55(11)3091-5317, Fax: +55(11)3091-5404. mailto:nelsonk@pea.usp.br 2 M. FORGHANI-ELAHABAD, N. KAGAN Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) set of node pairs with related demand values which should be satisfied. Therefore, the reliability of such a system is defined as the probability of transmitting all the required demands from the sources to the corresponding destinations concurrently [5, 8, 14, 16]. Although many algorithms have been proposed in the literature to address the problems, evaluating the system reliability is an NP-hard problem [3], and thus the problem continues to be interesting to investigate. To evaluate the reliability of an MFN with single source and destination nodes, many algorithms have been proposed in terms of minimal cuts (upper boundary points – UBPs or d-MCs) [5-8, 12, 15, 21] or minimal paths (lower boundary points – LBPs or d-MPs) [9-11, 13, 14, 16]. Once all the UBPs or LBPs are determined, the reliability can be calculated by using some techniques such as the inclusion–exclusion principle [6] or the sum of disjoint products (SDP) [2]. In [13], the notion of d-MP candidate was introduced, and it was demonstrated that the minimal elements of all the d-MP candidates are the set of all the LBPs. Afterwards, several algorithms have been proposed in the literature to address the problem [9-11, 13, 14]. The algorithms generally consist of two main stages; finding all the d-MP candidates, and then checking each candidate for being a d-MP. The focus of this work is on determining all the d-MPs (or LBPs) in an MNP-MFN. In general, to compute the system reliability of an MNP-MFN, one can find all the system state vectors under which all the given demands can be satisfied simultaneously, and then calculate the probability of such vectors according to the given probability distributions of the arcs’ capacities. To search for such vectors, it is usually assumed that all the required minimal paths or minimal cuts are at hand in advance [5-11, 13, 14], and after determining these vectors, the system reliability can be computed using some techniques such as the inclusion-exclusion principle [6] or the sum of disjoint products [2]. Lin and Yuan [14] considered an MNP-MFN and proposed an algorithm to evaluate the system reliability in terms of minimal paths. The algorithm first finds all the flow patterns which satisfy the demands, then transforms these patterns to system-state vectors (SSVs) which are D-MP candidates, and finally checks each candidate for being a minimal one to find all the LBPs. It is reminded that as there is a set D of the demand values in the multi-pair-node case, the SSVs are called D-MP rather than d-MP. The most time consuming part of the proposed algorithm in [14] is the checking process as it needs to compare all the candidates to each other. In [16], Lin and Yeng applied this algorithm to a real-world network, namely Taiwan Advanced Research and Education Network, for evaluating the reliability of a computer network with multiple sources. Chakraborty and Goyal [5] proposed a three-step algorithm in terms of minimal cuts which uses SDP technique to evaluate the reliability of an MNP-MFN. The notable point on the algorithm is that it considers all the arcs with two states of failure or fully working, whereas usually in the real-world networks it is possible to have multistate arcs. Here, considering the problem of determining all the LBPs in an MNP-MFN, some new results are presented. Based on the presented results, a simple improved algorithm is proposed to address the problem. The algorithm is illustrated through a benchmark network. The complexity results are computed, and accordingly the proposed algorithm is shown to be more efficient than the existing ones in the literature. The reminder of this work is organized as follows. Section 2 states the required notations and explains some preliminaries on computing the system reliability. In Section 3, an algorithm is proposed and illustrated through a benchmark example. Then, the complexity results are computed, and the algorithm is compared with an existing one in the literature. Section 4 concludes the work. 2. PRELIMINARIES Here, first the required notations, nomenclature, and assumptions are stated, and then some preliminaries on computing the system reliability are described. LOWER BOUNDARY POINTS IN A MULTISTATE FLOW NETWORK 3 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) 2.1. Notations, Nomenclature, and Assumptions Here, the required notations and assumptions are stated. Table 2.1. The required notations. G(N, A, M, Q) An MNP-MFN with N = {1, 2, ..., n} being the set of nodes (n is the number of nodes), A= {ai | 1 ≤ i ≤ m} being the set of arcs (m is the number of arcs), M = (M1, M2, ..., Mm) being a vector, where Mi denotes the maximum capacity of arc ai, for i = 1, 2, ..., m, and Q = {(i,j) | i is a source node with corresponding destination node j} being the set of all the node pairs. xi xi denotes the current capacity of the arc ai, for i = 1, 2, …, m. X X= (x1, x2, ..., xm) is a system-state vector representing the current capacities of all the arcs. di,j is a given demand of data (flow) to be transmitted from source node i to destination node j for every node pair (i, j) Q. v, w are the number of sources and destinations in the network, respectively. oi ,1 w i i jj o d   is the total flow outgoing from source node i, for i = 1, …, v. uj ,1 v j i jj u d   is the total flow incoming to destination node j, for j = 1, …, w. s, t are the added artificial source and destination nodes to the network. bi is the added artificial arc from node s to the source node i with the fixed capacity of oi, for i = 1, …, v. cj is the added artificial arc from the destination node j to node t with the constant capacity of uj, for j = 1, …, w. G is the new network after adding artificial nodes and arcs into G. V(X) is the maximum flow on the network G from node s to node t. Z(X) = {ai A | xi > 0} is the set of nonzero-capacity arcs, under X. ei = 0(ai) is a system-state vector in which the capacity level is 1 for ai and 0 for the other arcs. Hi,j is the set of all the minimal paths from source node i to destination node j, for every (i,j)  Q. H is the set of all the minimal paths in the network G, i.e., , ( , ) i j i j Q H H   . h is the number of all the minimal paths in G, i.e., h = |H|. Pj is the jth minimal path in G, for j = 1, …, h. CPj = min {Mi | ai Pj} is the capacity of Pj, for j = 1, 2, …, h. D = {di,j | (i, j) Q} is the set of all the demands in the network. σ is the number of all the D-MP candidates. A system state X = (x1, x2, ..., xm) is less than or equal to system state Y = (y1, y2, ..., ym), written as X ≤ Y, when xi ≤ yi, for i = 1, 2, ..., m, and also X < Y, when X ≤ Y with at least one j, j = 1, 2, ..., m, such that xj < yj. A vector X  is said to be a minimal vector when there is no vector Y  such that Y < X. A path is a sequence of adjacent arcs from a 4 M. FORGHANI-ELAHABAD, N. KAGAN Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) source node to a destination node, and a minimal path (MP) is a path with no cycle. The following assumptions are considered in this work: 1. Each node is perfectly reliable. 2. Each added artificial arc in G is perfectly reliable. 3. Flow in G and G satisfies the flow conservation law [1]. 4. The capacity of each arc ai in A is modelled as a non-negative integer-valued random number less than or equal to Mi. 5. The arcs’ capacities are statistically independent. 2.2. Reliability In a multi-node-pair multistate flow network (MNP-MFN), for each node pair (i, j) in Q, there is a demand dij of flow (data or commodity) to transmit from source node i to destination node j. Hence, the system reliability is the probability of all the demands being satisfied, that is for each node pair (i, j) in Q, at least dij units of flow (data) can be transmitted from node i to node j, simultaneously. To compute such a probability, one can first find the set of all the system-state vectors (SSVs) on which all the demands can be satisfied simultaneously, and then compute the probability of those SSVs. Thus, considering  = {X | X is an SSV on which all the demands can be satisfied concurrently}, we see that RD = Pr{X | X  }. Now, assuming min = {X | X is a minimal vector in  } = {X1, X2, …, Xδ} and Ai = {X | X ≥ Xi}, for i = 1, 2, …, δ, it is seen that 1 i i A     , and consequently the system reliability can be computed using methods such as inclusion-exclusion technique or sum of disjoint products (SDP) [2, 5]. For example, in SDP technique, it is set B1 = A1 and 1 1 rr r i i B A A     for each r = 2, …, δ, and then 1 Pr( )i D i R B    (2.1) Where Pr( ) Pr( ) i i X B B X    , and 1 Pr( ) Pr( )jj m X x    . Hence, to evaluate the reliability of an MNP-MFN, it is enough to find all the set min which is the set of all the lower boundary points (LBPs) in the network. The problem of finding all the LBPs is called D-MP problem in the literature [8, 13, 14, 16]. 3. MAIN BLOCK To find all the LBPs in an MNP-MFN, we first define the notion of flow pattern at level D (called D-FP) as follows. It is reminded that D is the set of all the demand values. Definition 3.1: A vector F = (f1, f2, …, fh) is named a flow pattern at level D (D-FP) when it satisfies the followings: , , : : ( ) , for all ( , ) , ( ) , 1,2,..., . i j l i l l i j l P H l i l a P I f d i j Q II f M i m             (3.1) It is noted that in a D-FP, the component fl shows the amount of flow on minimal path (MP), Pl, and this is why it is called a flow pattern. In the system (3.1), the first equation guarantees that the summation of flows on all the MPs from node i to node j is di,j, and so the given LOWER BOUNDARY POINTS IN A MULTISTATE FLOW NETWORK 5 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) demand can be satisfied. The second inequality guarantees that the summation of flows on each arc is less than the maximum capacity of the arc. For example, considering Q = {(1, 2), (1, 3), (4, 3)} as the set of node pairs in Fig. 1, the set of MPs are H1,2 = {{a1}, {a5, a4}}, H1,3 = {{a1, a2}, {a5, a6}, {a1, a3, a6}, {a5, a4, a2}}, H4,3 = {{a6}, {a4, a2}}, and hence H = {{a1}, {a5, a4}, {a1, a2}, {a5, a6}, {a1, a3, a6}, {a5, a4, a2}, {a6}, {a4, a2}}. Now, considering d1,2 = 1, d1,3 = 3, and d4,3 = 2 as the given demand values, and M = (3, 3, 2, 3, 2, 2) as the max-capacity vector, the set of all the D-FPs is obtained as follows. (0,1,3,0,0,0,2,0), (1,0,2,0,0,1,2,0), (0,1,2,0,0,1,2,0), (1,0,1,0,0,2,2,0), (0,1,2,0,1,0,1,1), (1,0,2,1,0,0,1,1), (0,1,2,1,0,0,1,1), (1,0,1,0,1,1,1,1), (0,1,1,0,1,1,1,1), (1,0,1,1,0,1,1,1), (1,0,0,0,1,2,1,1), (0,1,1,0,2,0,0,2), (1,0,1,1,1,0,0,2), (0,1,1,1,1,0,0,2), (1,0,1,2,0,0,0,2), (1,0,0,0,2,1,0,2), (1,0,0,1,1,1,0,2). Fig. 1. A benchmark example It is reminded that each D-FP shows the amount of flow on all the MPs, and hence for each D-FP, say F = (f1, f2, …, fh), one can find the corresponding system-state vector (SSV), X = (x1, x2, …, xm) using the following equation. : , 1,2,..., . i l i l l a P x f i m    (3.2) The SSV, X which is calculated through Eq. (3.2) above is called a D-MP candidate. A notable point is that as the number of MPs is usually far greater than the number of arcs in a network, it is possible to obtain duplicate D-MP candidates from different D-FPs, and so it is required to remove the duplicate candidates. For example, transforming the above-mentioned seventeen D-FP vectors in Fig. 1, only five different SSVs X1 = (3, 3, 0, 1, 1, 2), X2 = (2, 3, 0, 2, 2, 2), X3 = (3, 3, 1, 2, 1, 2), X4 = (2, 3, 1, 3, 2, 2), X5 = (3, 3, 2, 3, 1, 2) are obtained and the other twelve SSVs are duplicates. The following result proven in [13, 14] shows that to find all the LBPs, it is enough to first find all the D-MP candidates and then check each candidate for being an LBP. Lemma 3.1: Each LBP is a D-MP candidate. Proposition 3.1: There is a possibility of generating duplicate D-MP candidates from different D-FPs through Eq. (3.2). In fact, it can be considered as a common drawback in the presented works in the literature to not notice for generating duplicate candidates from different flow pattern vectors [8]. The first trivial method is to compare D-MP candidates for detecting and removing the duplicates. However, as they are m-tuple vectors, the time complexity of comparison process is relatively high. Hence, the proposed data structure in [7] is used here instead of comparing the vectors. Next, it is briefly explained how the duplicate candidates can be removed using the proposed data structure in [7]. Let M* = max {M1, M2, …, Mm}, X = (x1, …, xm) be a D- 6 M. FORGHANI-ELAHABAD, N. KAGAN Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) MP candidate, k be the number of digits in M*, and ki be the number of digits in xi, for i = 1, 2, …, m. Since xi ≤ Mi ≤ M*, for i = 1, …, m, it is clear that ki ≤ k. Now, to construct a k-digit number ni for component xi, if k = ki, then let ni = xi, and if ki < k, then let times 00...0 l i l k k n x   . Thereby, the ml-digit number 1 2...X mN n n n can be constructed associated with X. Corollary 3.1: The time complexity of removing the duplicate D-MP candidates by using the method above is O(σlogσ), where σ is the number of all the candidates. It should be noted that under each D-MP candidate X obtained by Eq. (3.2), when the flows are transmitting simultaneously from all the sources to all the destinations, the maximum flow from each source node i to the corresponding destination node j equals the sum of flows on all the MPs between them, that is exactly , ,: i j l l i jl P H f d   . Hence, the following result is at hand. Proposition 3.2: Under D-MP candidate X, the maximum flow between each node pair (i,j) in Q is exactly di,j when the flows are transmitting concurrently from all the sources to all the destinations. To find all the LBPs from all the candidates, the authors in [13, 14, 16] compared all the candidates to detect the minimal ones. However, the number of candidates grows exponentially with the size of network and as they are m-tuple vectors, it is really time consuming to compare all the candidates. Here, an improved technique is proposed to check each candidate to be an LBP. In fact, two artificial nodes and a few artificial arcs are added into the network to make use of max-flow algorithm for checking the D-MP candidates. For a given MNP-MFN, say G, first two artificial nodes s (a source) and t (a destination) are added to G. Then, from node s to each source node i, an artificial arc bi with the fixed capacity of ,1 w i i jj o d   is added, for i = 1, 2, …, v. Moreover, from each destination node j to node t, an artificial arc cj with the fixed capacity of ,1 v j i ji u d   is added, for j = 1, 2, …, w. The new network with artificial nodes and arcs is named G . For example, considering Q = {(1, 2), (1,3), (4,3)} as the set of node pairs, and D = {1, 3, 2} as the set of demand values in the given network in Fig. 1, the new network G with artificial nodes and arcs is constructed as given in Fig. 2. The capacities of b1, b2, c1, and c2 are respectively o1 = 4, o2 = 2, u1 = 1, and u2 = 5. Fig. 2. The benchmark with added artificial nodes and arcs. As the added artificial arcs are perfectly reliable with a constant capacity, they are not considered in the system state vectors (SSVs) of the network, and an SSV in G is still exhibited as X= (x1, x2, ..., xm) where m is the number of arcs in G. It is reminded that the LOWER BOUNDARY POINTS IN A MULTISTATE FLOW NETWORK 7 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) capacity of an artificial arc from node s to source node i is always assumed to be oi, for each i = 1, …, v, and the capacity of an artificial arc from destination node j to node t is always assumed to be uj, for j = 1, …, w. This way, it is possible to check all the node pairs’ demands by sending 1 1 v w i ji j d o u      units of flow from node s to node t. Corollary 3.2: 1 1 v w i ji j o u     . Proof. According to definition, we have ,1 w i i jj o d   , and consequently it is concluded that , ,1 1 1 1 1 1 v v w w v w i i j i j ji i j j i j o d d u               . □ Lemma 3.2: If X is a D-MP candidate, then V(X) = d in G , namely the maximum flow from node s to node t equals d, where 1 1 v w i ji j d o u      . Proof. First, the d units of flow from node s are transmitted through the artificial arcs bis to the source nodes (oi units on arc bi, for i = 1, 2, …, v), and then according to Proposition 2, these d unites of flow are transmitted from the source nodes to the destination nodes so that uj units of flow is received at destination node j, for j = 1, 2, …, w. Finally, according to considered capacities for the artificial arcs, the flows are transmitted to node t through the arcs cjs. This shows that V(X) = d which completes the proof. □ Theorem 3.1: A D-MP candidate X is an LBP if and only if for each ai in Z(X), we have V(X ei) < d in G . Proof. According to Lemma 1, each LBP is a D-MP candidate, and thus the first side has been already demonstrated. Now, assume that X is a candidate which is not an LBP (or equivalently a minimal vector in  ). Thus, there is a vector Y in  such that X > Y. Without loss of generality, assume that xl > yl, for an l. Since Y is a vector in  , all the demands are satisfied under Y, and so we have V(Y) ≥ d in G . Thus, we have V(X el) ≥ V(Y) ≥ d, and this contradicts the definition of X being a candidate. Hence, the proof is complete. □ Considering σ as the number of all the D-MP candidates, since each candidate is an m-tuple vector, the time complexity of comparing them is O(mσ2). Whereas considering the time complexity of max-flow algorithm as O(mn) [21], and that in the worst case the condition V(X ei) < d should be checked for all the m arcs, the time complexity of checking each candidate is O(m(m+v+w)(n+2)). Therefore, the time complexity of checking all the candidates is O(mnσ(m+v+w)) ≈ O(m2nσ) as the number of all the sources and sinks are usually less than m. It is clearly seen that the number of all the D-MP candidates, σ, is really far greater than mn, and thus our technique proposed here is highly more efficient than the proposed ones in [14, 16]. Lemma 3.3: The time complexity of using Theorem 2 to check each D-MP candidate for being an LBP is O(m2nσ). Now, we are at the position of stating our proposed algorithm for determining all the LBPs in an MNP-MFN. 8 M. FORGHANI-ELAHABAD, N. KAGAN Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) 3.1. The Proposed Algorithm Algorithm 1. (Find all the LBPs in an MNP-MFN) Input: An MNP-MFN, G(N, A, M, Q) along with the set of all the demand values, D. Output: The set of all the LBPs. Step 1. Let   (set of all the LBPs) and   (set of all the associated numbers). Then, compute ,1 w i i jj o d   , for i = 1, …, v, ,1 v j i ji u d   , for j = 1, …, w, and 1 v ii d o   . Afterwards, add the artificial nodes s and t and the related artificial arcs with fixed capacities into G, as explained in preceding section for constructing G . Step 2. Find a D-FP, say F = (f1, f2, …, fh) by solving the system (3.1). If there is no solution, skip to Step 7. Step 3. Considering D-FP, F, compute the SSV, XF = (x1, x2, ..., xm) through Eq. (3.2). Step 4. Compute the associated number NX with XF. If it is duplicate number, return to Step 2 to find the next D-FP, else add NX to  and determine Z(XF) = {ai in A | xi > 0}. Step 5. If Z(XF) =  then XF is a LBP, add it to  and return to Step 2 to find the next D-FP. Step 6. Select an arc in Z(XF), say ai, and remove it from Z(XF). If V(XF – ei) < d in G , then return to Step 5, else X is not a LBP, return to Step 2 to find the next D-FP. Step 7. Set  is the set of all the LBPs. Stop. The following example is provided to illustrate Algorithm 1. Example 3.1: There are two smart meters connected to two control centers in a smart grid. Each smart meter may need to transmit some data on the network to one or both control centers. Assume that the network is the one given in Fig. 1 in which nodes 1 and 4 are the smart meters and nodes 2 and 3 are the control centers. As it is seen in Fig. 1, there are some arcs (links) between the smart meters and control centers to transmit data on. Suppose that the first smart meter (node 1) needs to send one unit of data to the first control center (node 2) and three units of data to the second control center (node 3) per hour. Moreover, the second smart meter (node 4) needs to send only two units of data to the second control center (node 3) per hour. If the maximum capacities of the arcs in the network are given by M = (3, 3, 2, 3, 2, 2), the manager needs to know the reliability of the network to satisfy the demands. The probability distributions for the arcs’ capacities are given in Table 2. Solution: To compute the reliability of the system, Algorithm 1 is employed as follows. Step 1. Let   ,   . Then, we have o1 = 1+3 = 4, o2 = 2, u1 = 1, u2 = 2 + 3 =5, and d =6. Afterwards, G is obtained as given in Fig. 2. Step 2. The D-FP, F = (0,1,3,0,0,0,2,0) is obtained by solving the system (3.1). Step 3. The corresponding SSV, X = (3, 3, 0, 1, 1, 2) is obtained through Eq. (3.2). Step 4. The associated number with X is NX = 330112 which is not duplicate, and so we have  = {330112} and Z(X) = {a1, a2, a4, a5, a6}. Step 5. Z(XF)  . Step 6. Arc a1 is selected and let Z(X) = {a2, a4, a5, a6}. Since V(2, 3, 0, 1, 1, 2) = 5<6, the transfer is made to Step 5. Step 5. Z(X) = {}, and hence X is an LBP, letting  = {(3, 3, 0, 1, 1, 2)}, and transfer is made to Step 2. LOWER BOUNDARY POINTS IN A MULTISTATE FLOW NETWORK 9 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Finally,  = {(3, 3, 0, 1, 1, 2), (2, 3, 0, 2, 2, 2)} is obtained. It is noted that among the seventeen D-FPs, only five unduplicated D-MP candidates are obtained containing only two LBPs. It is also noted that all the D-FPs and D-MP candidates for this example have already stated in the previous sections. Now, to compute the system reliability by using the SDP technique, let A1 = {X | X ≥ X1 = (3, 3, 0, 1, 1, 2)}, A2 = {X | X ≥ X2 = (2, 3, 0, 2, 2, 2)}, B1 = A1, and B2 = A2 – A1. Thereby, the system reliability is equal to 1 2 1 2 3 4 5 6 1 2 3 4 5 6 9 7 Pr( ) Pr( ) Pr( 3) Pr( 3) Pr( 0) Pr( 1) Pr( 1) Pr( 2) Pr( 2) Pr( 3) Pr( 0) Pr( 2) Pr( 2) Pr( 2) 8 75 1 95 95 85 10 1 75 1 9 9 85 10 0.460275 0.0516375 0.5119125. DR B B x x x x x x x x x x x x                                              Table 1. Probability distributions for arcs’ capacities of Fig. 1. Arc Capacity and probability 0 1 2 3 a1 0.05 0.05 0.10 0.80 a2 0.05 0.10 0.10 0.75 a3 0.05 0.05 0.90 0 a4 0.05 0.05 0.05 0.85 a5 0.05 0.05 0.90 0 a6 0.10 0.05 0.85 0 3.2. Complexity Results The time complexity of Step 1 is O(v + w). Assuming the number of all the D-FPs as σ, the complexity of solving the system (3.1) in Step 2 to find all the D-FPs is of order of O(hσ) [7]. Step 3 is of order of O(mh) for constructing each D-MP candidate, and thus is of order of O(mhσ) for computing all the candidates. According to Corollary 1, the time complexity of Step 4 is O(σlogσ). Steps 5 and 7 are of order of O(1). According to Lemma 3, the time complexity of Step 7 is O(m2nσ). As a result, the time complexity of Algorithm 1 is O(mhσ + σlogσ + m2nσ). By the way, in large networks, h grows exponentially with increasing m and n, and thus h m, n, and consequently the time complexity of Algorithm 1 is O(mhσ) for large networks. Theorem 3.2: The time complexity of Algorithm 1 for large network is O(mhσ). 3.3. Comparison results Here, the proposed algorithm in [14] is compared with Algorithm 1 proposed here. As the proposed algorithm in [14] needs to solve the system (3.1) to find all the D-FPs, and also compares all the D-MP candidates to remove the duplicates and detect the minimal ones, the time complexity of this algorithm is at least O(mhσ + mσ2) = O(mσ2), where the first part is for solving the system (3.1) and the second part is for the comparison process. It should be kept in mind that each D-MP candidate is an m-tuple vector. Even in small network such as 10 M. FORGHANI-ELAHABAD, N. KAGAN Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) the given benchmark in Fig. 1 the number of D-FPs, i.e., σ, is really greater than the number of MPs, i.e., h. Hence, the time complexity of the proposed algorithm in [14] is highly greater than the one for Algorithm 1, the proposed algorithm here. It should be noted that in Example 1, the proposed algorithm in [14] needs to compare seventeen 6-tuple vectors, that is 102 comparison job, to remove the duplicates and find the five D-MPs, while Algorithm 1 needs only to compare seventeen numbers, that is seventeen comparison job, to do the same work. It should be noted that as the number of D-FPs is increased exponentially with increasing the size of the network, the practical efficiency of our proposed algorithm will be notable in large networks in comparison with the one proposed in [14]. 5. CONCLUSION Reliability evaluation of multistate flow networks (MFNs) has been a very attractive problem in the recent decades among the researchers from several research areas. Majority of the proposed algorithms have considered a single source-destination MFN whereas the real- world systems generally contain more than one node pair, and can be modeled as multiple- node-pair MFNs (MNP-MFNs). The reliability of an MNP-MFN can be computed in terms of minimal paths by determining all the lower boundary points (LBPs) or in terms of minimal cuts by computing all the upper boundary points. Here, for evaluating the reliability of an MNP-MFN, the problem of determining all the LBPs in such a network was considered. Some results were presented to improve the solution. Based on the results, a simple improved algorithm was proposed to address the problem. The algorithm was illustrated through a benchmark example. The complexity results were computed. The algorithm was shown to be more efficient than an existing one based on the complexity results and the illustrative example. ACKNOWLEDGEMENTS The authors thanks FAPESP (Grant 15/21924-1) for supporting this work. REFERENCES 1. Ahuja, R.K., Magnanti, T.L. & Orlin J.B. (1993). Network flows theory, algorithms, and applications. New Jersey: Englewood Cliffs, Prentice-Hall Int. 2. Balan, A.O. & Traldi, L. (2003). Preprocessing minpaths for sum of disjoint products. IEEE Transactions on Reliability, 52 (3), 289–295. 3. Ball, M.O. (1980). Complexity of network reliability computations. Networks 10 (2), 153–165. 4. Boesch, F.T., Satyanarayana, A. & Suffel, C.L. (2009). A survey of some network reliability analysis and synthesis results. Networks 54 (2), 99–107. 5. Chakraborty, S. & Goyal, N.K. (2017). An efficient reliability evaluation approach for networks with simultaneous multiple-node-pair flow requirements. Quality and Reliability Engineering International 33, 1067–1082. 6. Forghani-elahabad, M. & Mahdavi-Amiri, N. (2013). On search for all d-MCs in a network flow, Iranian Journal of Operations Research, 4 (2), 108-126. 7. Forghani-elahabad, M. & Mahdavi-Amiri, N. (2016a). An improved algorithm for finding all upper boundary points in a stochastic-flow network. Applied Mathematical Modelling 40 (4), 3221–3229. LOWER BOUNDARY POINTS IN A MULTISTATE FLOW NETWORK 11 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) 8. Forghani-elahabad, M. & Mahdavi-Amiri, N. (2016b). Reliability assessment of a multi-source multi-sink stochastic-flow network in terms of minimal paths. Proceeding of 9th International Iranian Operation Research Conference, 1065–1069. 9. Forghani-elahabad, M. & Mahdavi-Amiri, N. (2016c). A new algorithm for generating all minimal vectors for the q SMPs reliability problem with time and budget constraints, IEEE Transactions on Reliability, 65 (2), 828-842. 10. Forghani-elahabad, M. & Bonani, L. (2017). Finding all the lower boundary points in a multistate two-terminal network. IEEE Transactions on Reliability 66 (3), 677–688. 11. Forghani-elahabad, M. & Kagan, N. (2018). Reliability evaluation of a stochastic- flow network in terms of minimal paths with budget constraint, IISE Transactions, In press. DOI: https://doi.org/10.1080/24725854.2018.1504358. 12. Forghani-elahabad, M. & Kagan, N. (2019). Assessing reliability of multistate flow networks under cost constraint in terms of minimal cuts, International Journal of Reliability, Quality and Safety Engineering, In production. 13. Lin, J.S., Jane, C.C. & Yuan, J. (1995). On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks 25, 131–138. 14. Lin, Y.K. & Yuan, J. (2003). Flow reliability of a probabilistic capacitated-flow network in multiple node pairs case. Computers & Industrial Engineering 45, 417– 28. 15. Lin, Y.K. & Yeh, C.T. (2011). Maximal network reliability for a stochastic power transmission network. Reliability Engineering & System Safety 96, 1332–39. 16. Lin, Y.K. & Yeng, L.C.L. (2013). Network reliability based decision of Internet with multiple sources and multiple sinks. Decision Support Systems 54, 1477–1487. 17. Locks, M.O. (1985). Recent developments in computing of system-reliability. IEEE Transactions on Reliability R-34 (5), 425–436. 18. Padmavathy, N. & Chaturvedi, S.K. (2013). Evaluation of mobile ad hoc network reliability using propagation-based link reliability model. Reliability Engineering & System Safety, 15, 1–9. 19. Ramirez-Marquez, J.E. & Rocco, C.M. (2008). All-terminal network reliability optimization via probabilistic solution discovery. Reliability Engineering & System Safety, 93, 1689–97. 20. Rausand, M. & Hoyland, A. (1994). System Reliability Theory: Models, Statistical Methods, and Applications. New York: Wiley-Interscience. 21. Orlin, J. B. (2013). Max flows in O(nm) time or better. Proceedings of forty-fifth annual ACM Symposium on Theory of Computing, 765–774. 22. Wu, W.W., Ning, A. & Ning, X.X. (2008). Evaluation of the reliability of transport networks based on the stochastic flow of moving objects. Reliability Engineering & System Safety 93, 838–44. https://doi.org/10.1080/24725854.2018.1504358