Compact models for Critical Node Detection in telecommunication networks

Abstract

Given a network defined by a graph, a weight associated to each node pair and a positive parameter p, the CND problem addressed here is to identify a set of at most p critical nodes minimizing the total weight of the node pairs that remain connected when all critical nodes are removed. We improve previously known compact models and present computational results, based on telecommunication backbone networks, showing that the proposed models are much more efficiently solved and enable us to obtain optimal solutions for networks up to 200 nodes and p values up to 20 critical nodes within a few minutes in the worst cases.