Graph Spanners

• Grant number: 13/22875-9
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: March 01, 2014
• End date: 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

Abstract

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.

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.