Critical node detection with connectivity based on bounded path lengths

Abstract

For a given graph representing a transparent optical network, a given weight associated to each node pair and a given positive integer c, the Critical Node Detection problem variant addressed here is the determination of the set of c nodes that, if removed from the graph, minimizes the total weight of the node pairs that remain connected. In the context of transparent optical networks, a node pair is considered connected only if the surviving network provides it with a shortest path not higher than a given positive value T representing the optical transparent reach of the network. Moreover, the length of a path depends both on the length of its links and on its number of intermediate nodes. A path-based Integer Linear Programming model is presented together with a row generation approach to solve it. We present computational results for a real-world network topology with 50 nodes and 88 links and for c=2 up to 6. The optimal results are compared with node centrality based heuristics showing that such approaches provide solutions which are far from optimal.