Advanced search
Start date

Graph Spanners

Grant number: 13/22875-9
Support Opportunities:Scholarships in Brazil - Doctorate
Effective date (Start): March 01, 2014
Effective date (End): February 28, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Yoshiko Wakabayashi
Grantee:Hugo Vinicius Vaz Braga
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil


In this project we plan to investigate problems on graph spanners. Given a connected graph G and a positive real number t>1 (stretch factor), a t-spanner is a spanning subgraph H of G such that for every pair of vertices u, v the distance between u and v in H is at most t times their distance in G. A central problem on this topic, known as the 'minimum t-spanner problem', consists in finding in a given connected graph G a t-spanner with the least possible number of edges. When the objective is to find (if existent) a t-spanner that is a tree, then we have the 'tree t-spanner problem'. Both problems are computationally hard when t is at least 4. In this project, we focus on graph spanners problems, with emphasis on their algorithmic and computational complexity aspects. We shall give special attention to the tree t-spanner problem, but our study will not restrict to it. Spanners have applications in communication networks, distributed systems, robotics and other areas.

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

Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
BRAGA, Hugo Vinicius Vaz. Exact algorithms for spanner problems in graphs. 2018. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.

Please report errors in scientific publications list using this form.