Personal tools
You are here: Home CG seminar 2021 Reliable spanners
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
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