On the Complexity of Disaster-Aware Network Extension Problems

In this paper, we deal with the complexity of problems related to finding cost-efficient, disaster-aware cable routes. In particular, we compare two very different versions of the problem. In the first version, only the worst-case scenarios are considered, while in the second, the probability of the...

Full description

Saved in:
Bibliographic Details
Main Authors: Vass, Balazs, Branyi, Balazs, Nagy, Beata Eva, Tapolcai, Janos
Format: Conference Proceeding
Language:English
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we deal with the complexity of problems related to finding cost-efficient, disaster-aware cable routes. In particular, we compare two very different versions of the problem. In the first version, only the worst-case scenarios are considered, while in the second, the probability of the disasters is also known, and the aim is to find the most cost-efficient solution in terms of investment cost and risk of a network outage. Worstcase computations allow using efficient computational geometry algorithms, and even large networks can be analyzed. On the other hand, to find the cost-efficient soltuion, a lot of empirical hazard data must be processed, and heavy algorithms must be used. In this paper, we study the benefits and drawbacks of each model. In particular, we define multiple versions of the problem and investigate their complexity.
ISSN:2576-3539
DOI:10.1109/RNDM55901.2022.9927678