A spanner of a graph is a spanning subgraph that preserves pairwise distances up to a specified error factor. Spanners are often sparse and have light weight, and thus have found numerous practical applications, for example, in network design, distributed computing, approximation algorithms. In 1996, Halperin and Zwick designed a linear time algorithm to find a (conjecturally) optimal sparse spanner for general graphs. However, a linear-time algorithm for constructing (conjecturally) optimal light-weight spanners remains elusive. In this talk, I will describe the first (nearly) linear time algorithm to construct such a spanner. This talk is based on joint work with Shay Solomon from Tel Aviv University.
To join this virtual meeting via Zoom, click here.
This Zoom meeting requires a passcode. Email organizers Cameron Musco or Rik Sengupta if you need the Zoom password, or see emails on the seminars list.