דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Distributed Approximation for Tree Augmentation
event speaker icon
מיכל דורי, הרצאה סמינריונית למגיסטר
event date icon
יום ראשון, 26.3.2017, 11:30
event location icon
טאוב 301
A minimum spanning tree is an essential structure for distributed algorithms, since it is a low-cost connected subgraph which provides an effcient way to communicate in a network. However, trees cannot survive even one link failure. In this talk, we study the Tree Augmentation Problem (TAP), for which the input is a graph G and a spanning tree T of G and the goal is to augment T with a minimum (or minimum weight) set of edges, such that the new graph survives any single link failure. Being central tasks for network design, TAP and additional connectivity augmentation problems have been well studied in the sequential setting. However, despite the distributed nature of these problems, they have not been studied in the distributed setting. In this talk, we address this fundamental topic and present distributed 2-approximation algorithms for TAP, both for the unweighted and weighted versions.
[בחזרה לאינדקס האירועים]