Minimum-cost Subgraph Satisfying the Connectivity Requirement
David Adjiashvili
Progress in Signals and Telecommunication Engineering, Vol. 13, No. 1, 2024.
DOI: https://doi.org/10.6025/pste/2024/13/1/1-17
Link: https://www.dline.info/pste/fulltext/v13n1/pstev13n1_1.pdf
Abstract:
In this work, we work on robust models, i.e. ones that incorporate uncertainty in the feasible set. The aim is to find a minimum-cost subgraph satisfying the connectivity requirement. Most existing models of robust network design assume uniform scenario sets. Our algorithm combines combinatorial and LP-based techniques. We are convinced our methods are suitable for solving other robust problems in planar graphs.