Advanced search
Start date

Problems on spanners in graphs

Grant number: 19/14471-1
Support Opportunities:Scholarships in Brazil - Post-Doctoral
Effective date (Start): February 01, 2020
Effective date (End): February 28, 2023
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Renzo Gonzalo Gómez Diaz
Host 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


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

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
GOMEZ, RENZO; GUTIERREZ, JUAN. Path eccentricity of graphs. DISCRETE APPLIED MATHEMATICS, v. 337, p. 13-pg., . (19/14471-1)
GOMEZ, RENZO; MIYAZAWA, FLAVIO KEIDI; WAKABAYASHI, YOSHIKO. Improved NP-hardness results for the minimum t-spanner problem on bounded-degree graphs. THEORETICAL COMPUTER SCIENCE, v. 947, p. 13-pg., . (15/11937-9, 19/14471-1, 16/01860-1)

Please report errors in scientific publications list using this form.