The University of Arizona
Please note that this event has ended!

Spanners in Graphs

TRIPODS Seminar

Spanners in Graphs
Series: TRIPODS Seminar
Location: Online
Presenter: Richard Spence, University of Arizona Department of Computer Science

A spanner of a given graph is a sparse subgraph which approximately preserves distances of the original graph, up to some error. Spanners have application in many areas including graph compression, computing approximate all-pairs shortest distances, and motion planning. In this talk, we survey some theoretical results involving the size or lightness of spanners with a given error, including those on multiplicative and additive spanners, as well as recent results on additive spanners in weighted graphs. We conclude with open problems in this area.