Advanced search
Start date
Betweenand

Problems on spanners in graphs

Grant number: 19/14471-1
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): February 01, 2020
Effective date (End): January 31, 2023
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Flávio Keidi Miyazawa
Grantee:Renzo Gonzalo Gómez Diaz
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated research grant:15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

The objective of this project is to study problems concerning graph spanners. Given a connected graph G and a positive real number t > 1 (stretch factor), a t-spanner of G is a spanning subgraph H of G such that for every pair of vertices u and v, the distance between u and v in H is at most t times the distance between them in G. A central problem about spanners, known as the tree t-spanner problem, asks to find, given a connected graph G, a tree that is a t-spanner of G, or conclude that such tree does not exist. When the objective is to find a t-spanner subgraph with the minimum number of edges, we obtain the minimum t-spanner problem. For fixed t, the case t = 3 is the only one for which the computational complexity has not been established yet. In this project our aim is to study problems involving graph spanners, with focus on their algorithmic aspect and computational complexity. We are interested in discovering new classes of graphs, for which those problems are polynomially solvable. Also, we will focus on the case t = 3. We plan to investigate these problems with new approaches (approximation algorithms or exact methods) to contribute with algorithmic and complexity results that advance the state of the art of this field. (AU)

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

Please report errors in scientific publications list by writing to: cdi@fapesp.br.