Personal tools
You are here: Home CG seminar 2021 Reliable spanners
« January 2022 »
January
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
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