Personal tools
You are here: Home CG seminar 2021 Reliable spanners
« October 2021 »
October
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
Log in


Forgot your password?
 

Reliable spanners

Wednesday, November 4th, 16:10

underline

Sariel Har-Peled, UIUC

Abstract:

A spanner is reliable if it can withstand large catastrophic
failures in the network. More precisely, any failure of some nodes can
only cause a small damage in the remaining graph in terms of the
dilation. That is, the spanner property is maintained for almost all
the nodes in the residual graph. We will discuss recent results on
this problem, including (a) constructions of reliable spanners of near
linear size in the low-dimensional Euclidean settings, and (b)
constructions of reliable spanners for planar graphs, trees and
(general) metric spaces.

Based on joint work with Kevin Buchin and Dániel Olah, in the
following papers:

https://arxiv.org/abs/2007.08738
https://arxiv.org/abs/1912.01547
https://arxiv.org/abs/1811.06898
 
Document Actions