Advanced search
Start date

Connectivity augmentation in graphs and robust networks

Grant number: 21/12599-0
Support Opportunities:Scholarships in Brazil - Master
Effective date (Start): March 01, 2022
Effective date (End): November 30, 2023
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Yoshiko Wakabayashi
Grantee:Gabriel Morete de Azevedo
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated research grant:15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM
Associated scholarship(s):22/15632-1 - Connectivity augmentation in graphs and robust networks, BE.EP.MS


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.

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.