Connectivity augmentation in graphs and robust networks

Abstract

This is a research project to be carried out by Gabriel Morete de Azevedo towards a MSc degree under the guidance of Y. Wakabayashi at IME-USP. It is a project in combinatorial optimization that addresses problems on connectivity augmentation of graphs, with emphasis on their algorithmic aspects. Generally speaking, the goal of the problems to be investigated is to increase the connectivity of an input graph, by adding edges from a given set of links with non-negative costs, while minimizing the total cost. Some variants of these problems will be investigated, considering vertex-connectivity or edge-connectivity. When the graph models, for example, a telecommunication or a power transmission network, these parameters indicate the robustness (degree of fault tolerance) of the network, being of great interest both from practical and theoretical viewpoint. In general, such problems are all computationally difficult. By studying many different problems and algorithms, the candidate will be exposed to several techniques that are important to build a solid background in combinatorial optimization, in particular, in design of approximation algorithms.