Graph Spanners

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.