Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/26181
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 |
URI: | http://hdl.handle.net/10773/26181 |
DOI: | 10.1007/978-3-030-10731-4_2 |
ISBN: | 978-3-030-10730-7 |
Publisher Version: | https://link.springer.com/chapter/10.1007%2F978-3-030-10731-4_2 |
Appears in Collections: | CIDMA - Comunicações DETI - Comunicações IT - Comunicações |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
IO2018_finalV3.pdf | final draft post-refereeing | 226.1 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.