The Robust Node Selection Problem aiming to Minimize the Connectivity Impact of any Set of p Node Failures

摘要

Consider a network defined by an undirected graph and a positive weight assigned to each pair of nodes of a given network. For a positive integer parameter p, the critical node detection (CND) problem aims to identify a set of p nodes that minimizes the network weighted connectivity, i.e., the total weight of the node pairs that remain connected if p nodes fail. The minimum weighted connectivity provided by CND is used as the network vulnerability metric since it represents the lowest network weighted connectivity guaranteed for any set of p node failures. Also consider that any node can be made robust such that it never fails. For a positive integer parameter r, we define the robust node selection (RNS) problem as the selection of a set of r nodes that, if made robust, minimizes the connectivity impact of any set of p node failures by maximizing the minimum weighted connectivity provided by CND. We propose both an exact and a heuristic method to solve RNS and present computational results based on networks with up to 75 nodes. The computational results demonstrate the limits up to where the exact method can compute optimal solutions and the efficiency of the proposed heuristic for finding good quality solutions when the exact method is computationally expensive.