Title: Progress and challenges for labeling schemes (slides in PDF)
Cyril Gavoille (University of Bordeaux, France)
http://dept-info.labri.fr/~gavoille/
Abstract: A fundamental question in Distributed Computing is to understand how localized and how much information are required to solve a task on a network. Typically, if the distance between any pair x,y of nodes in a network is asked, we would like to know which minimal information about x and y in the network are needed. The goal in labeling schemes is precisely to understand how much information must be attached to the nodes (formalized as labels) to solve a graph problem assuming the answer can be determined solely on the basis of the labels of the nodes invoked in the query. In this talk, I give a survey on labeling schemes, present some recent results with their techniques, and highlight new challenges.
