Critical Node Detection with Connectivity Based on Bounded Path Lengths
Barbosa, F.
;
Agra, A.
;
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
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.