Advanced search
Start date

Connectivity augmentation in graphs and robust networks

Grant number: 22/15632-1
Support Opportunities:Scholarships abroad - Research Internship - Master's degree
Effective date (Start): February 01, 2023
Effective date (End): May 31, 2023
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Yoshiko Wakabayashi
Grantee:Gabriel Morete de Azevedo
Supervisor: Joseph Cheriyan
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Research place: University of Waterloo, Canada  
Associated to the scholarship:21/12599-0 - Connectivity augmentation in graphs and robust networks, BP.MS


This is the BEPE-MS research proposal of Gabriel Morete de Azevedo, M.Sc. student at 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. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list using this form.