Informative labeling schemes

Resumen:

Network representations play an important role in many domains of computer science, ranging from data structures and graph algorithms, to parallel and distributed computing, and communication networks. Traditional network representations are usually global in nature. That is, in order to retrieve useful information, one must access a global data structure representing the entire network, even if the desired information is solely local, pertaining to only a few nodes. In contrast, the notion of informative labeling schemes  suggests  the use of a local representation of the network. The principle is to associate a label with each node, selected in a way that enables to infer information about any two nodes directly from their labels, without using any additional sources  of information. Hence in essence, this method bases the entire representation on the set of labels alone. Obviously, labels of unrestricted size can be used to encode any desired information, including in particular the entire graph structure. The focus is thus on informative labeling schemes which use labels as short as possible.

This talk will introduce the notion of informative labeling scheme to the audience, and will survey some of the important results achieved in this context. In particular, we will focus on the design of compact adjacency-, ancestry-, routing-, and
distance-labeling schemes for trees. These schemes find applications in various contexts, including the design of small universal graphs, and the design of small universal posets.