A reversing traversal algorithm to predict deleting node for the optimal k-node set reliability with capacity constraint of distributed systems

A k-node set reliability with capacity constraint is defined as the probabi lity that a set, K, of nodes is connected in a distributed system and the t otal capacity of the nodes in K is sufficient under a given capacity. This is generally an NP-hard problem. For reducing computational time, a reasona ble k-node set within a given capacity constraint must be determined by an efficient algorithm. In this work, we propose a reversing traversal method to derive a k-node set under capacity constraint having an approximate solu tion. Initially, the set K is assigned to all the nodes in a system. The pr oposed algorithm uses an objective function to evaluate the fitness value o f each node in K and predict a deleting node, which is not a critical node, in K with minimal fitness value. After deleting the node, the fitness valu e of each node that is adjacent to the deleted node is tuned. The above two processes are repeated until the total capacity of the nodes in each subse t of the set K does not satisfy the capacity constraint. In our simulation, the proposed method can obtain an exact solution above 90%. When a sub-opt imal solution is obtained, the average deviation from an exact solution is under 0.0033. Computational results demonstrate that the proposed algorithm is efficient in execution time and effective for obtaining an optimal k-no de set with capacity constraint. (C) 2001 Elsevier Science B.V. All rights reserved.