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: