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 fi…