Critical Node Detection with Connectivity Based on Bounded Path Lengths
Sousa, A. F.
Critical Node Detection with Connectivity Based on Bounded Path Lengths, Proc Congresso da APDIO, Aveiro, Portugal, Vol. 278, Springer Proceedings in Mathematics & Statistics (2019), pp. 15 - 28, September, 2018.
Digital Object Identifier: 10.1007/978-3-030-10731-4_2
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.