- Graph Connectivity Augmentation
Krishnaiyan "KT" Thulasiraman, Subramanian Arumugam, Andreas Brandstädt, Takao Nishizeki · 2016
The problem of economically improving a network to meet given survivability requirements occurs in a number of areas. A straightforward problem of this type is concerned with creating more connections in a telephone or computer network so that it survives the failure of a given number of cables or terminals [1]. Similar problems arise in graph drawing [2], statics [3], and data security [4]. It is natural to model these networks by graphs or directed graphs and use graph connectivity parameters to handle the survivability requirements. This leads to the following quite general optimization problem.