Dynamic Algorithms via Forbidden-Set Labeling
Résumé
Forbidden-set labeling schemes is a way to associate with each node of a graph G a compact data-structure, i.e., a short label, supporting queries Q(s,t,X) between any two nodes (s,t) of G\X where X is any set of "forbidden" nodes of G. The query Q(s,t,X) must be solved from the labels of the nodes involved in the query only, without any other source of information. Several important distributed applications are captured by this framework, like for instance fault-tolerant and policy routing in the Internet. In this talk, I show how to derive new time-efficient algorithms for some problems in dynamic graphs.