Creating and sharing knowledge for telecommunications

Compact Models for Critical Node Detection in Telecommunication Networks

Santos, D. ; Sousa, A. F. ; Monteiro, P.

Electronic Notes in Discrete Mathematics Vol. 64, Nº 1, pp. 325 - 334, February, 2018.

ISSN (print): 1571-0653
ISSN (online):

Scimago Journal Ranking: 0,35 (in 2018)

Digital Object Identifier: 10.1016/j.endm.2018.02.007

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.