Please use this identifier to cite or link to this item:
Title: Critical node detection with connectivity based on bounded path lengths
Author: Barbosa, Fábio
Agra, Agostinho
de Sousa, Amaro
Keywords: Critical node detection
Transparent optical networks
Path model
Decomposition approach
Issue Date: 2019
Publisher: Springer International Publishing
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.
Peer review: yes
DOI: 10.1007/978-3-030-10731-4_2
ISBN: 978-3-030-10730-7
Publisher Version:
Appears in Collections:CIDMA - Comunicações
DETI - Comunicações
IT - Comunicações

Files in This Item:
File Description SizeFormat 
IO2018_finalV3.pdffinal draft post-refereeing226.1 kBAdobe PDFrestrictedAccess

Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.