Optimal Size Multiplicative Spanners of Weighted Graphs

ABSTRACT
A spanner is a sparse subgraph that preserves pairwise distances within some pre-specified dilation. We describe a simple randomized algorithm for constructing a family of optimal sized stretch 2k-1 spanner of weighted graphs that runs in linear expected time. The underlying construction and techniques are quite elementary and accessible even to upper level undergraduate students. Joint work with Surender Baswana.

SPEAKER BIO:
Sandeep Sen obtained his PhD from Duke University and after a brief stint in Bell Labs, Murray Hill, was on the faculty of Computer Science Department in IIT Delhi. He has been at Shiv Nadar University for the past 3 years as Dean of School of Engineering. A Fellow of the Indian National Science Academy and the Indian Academy of Sciences, his research interests span Algorithms and Theoretical Computer Science.