Connectivity augmentation in graphs and robust networks

Abstract

This is the BEPE-MS research proposal of Gabriel Morete de Azevedo, M.Sc. studentat the Institute of Mathematics and Statistics of the University of São Paulo, to be conducted at the Combinatorics & Optimization Department of the University of Waterloo,under the supervision of Professor Joseph Cheriyan. 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.