A survey on approximating spanners

14^th January 2014, 16:00 Ashton Lecture Theater
Prof Guy Kortsarz
Department of Computer Science
Rutgers University-Camden
USA

Abstract

Given an edge weighted graph G(V,E) a k-spanner of this graph is a graph G'(V,E') so that for every vertex pair, their distance in G' increases by no more than k factor compared to G.

Spanners have applications in routing over the internet, making asynchronous distributed system into a synchronous one, biology and much more.

Our goal, usually, is to get a spanner with few edges, and/or low cost. For example, I will show that there always exists a 3-spanner with O(n\sqrt{n}) edges and for some graph this is best possible.

The talk is a survey and large parts of it should be understood by people with basic knowledge of graphs and NP completeness.