Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 07, 2022, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Michal Dory
Assume that you have a huge graph, where edges and vertices may fail, and you want to answer questions about this graph quickly, without inspecting the whole graph. A fault-tolerant labeling scheme allows us to do just that. It is a distributed data structure, in which each vertex and edge is assigned a short label, such that given the labels of a pair of vertices s,t, and a set of failures F, you can answer questions about s and t in G\F. For example, determine if s and t are connected in G\F, just by looking at their labels. I will discuss a recent work where we show the first fault-tolerant connectivity labeling schemes for general graphs. I will also show applications for fault-tolerant routing. Here the goal is to provide each vertex a small routing table, such that given these tables we can efficiently route messages in the network, even in the presence of failures. Based on a joint work with Merav Parter.
Automatic MiSe System Software Version 1.4803M | admin login