UNAM
Usted está aquí: Inicio / Actividades académicas / Coloquios / Coloquio de Ciudad Universitaria / Actividades del Coloquio / Introduction to additive spanners

Introduction to additive spanners

Ponente: Shiri Chechik
Institución: Tel-Aviv University
Tipo de Evento: Investigación

Cuándo 01/09/2015
de 11:00 a 12:00
Dónde Auditorio "Alfonso Nápoles Gándara"
Agregar evento al calendario vCal
iCal

Abstract:

A graph spanner is a sparse subgraph of a given graph that approximately preserves the pairwise distances of the original graph.

Graph spanners were extensively studied since their introduction in the late 80's, and they are considered a fundamental structure as they are a key ingredient in many applications in distributed computation.

Much of the previous work focuses on multiplicative spanners, that is when the approximation guarantee is measured by the worst case ratio between distances in the spanner and distances in the original graph.

A much stronger guarantee is to obtain additive approximation, i.e., finding spanners whose distances are at most the distances in the original graph plus some additive term.

In this talk an introduction to spanners will be given and in particular additive spanners.

archivado en: