Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks |
| |
Authors: | Grigory Pastukhov Alexander Veremyev Vladimir Boginski Eduardo L Pasiliao |
| |
Institution: | 1. Industrial and Systems Engineering Department, University of Florida, 303 Weil Hall, Gainesville, FL, 32611, USA 2. Air Force Research Laboratory, Munitions Directorate, Eglin AFB, FL, 32542, USA
|
| |
Abstract: | We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|