UNAM
Usted está aquí: Inicio / Actividades académicas / Coloquios / Coloquio de Ciudad Universitaria / Actividades del Coloquio / Informative labeling schemes

Informative labeling schemes

Pierre Fraigniaud (CNRS y Université Paris Diderot) - martes 12 de abril, 12:00 horas
Ponente: Pierre Fraigniaud (CNRS y Université Paris Diderot)

Cuándo 12/04/2011
de 12:00 a 13:00
Dónde Salón "Graciela Salicrup"
Agregar evento al calendario vCal
iCal

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.

 

archivado en: