Mar 2022

Compact local certification of graph classes

Tipo de Evento: Seminario
Organiza: Facultad de Ingeniería y Ciencias
Dónde: Vía Zoom
Público: Abierto a todo público
Horario: 14:30:00 hr
Accede aquí

There are more and more distributed algorithms specially designed to work on specific graph classes, such as interval graphs or planar graphs. Before running such algorithms, one would like to be sure that the graph does belong to the class. In this talk, we tackle the problem of locally certifying graph classes.  Specifically, we explain recent results showing the design compact certification (i.e. proof-labeling schemes with logarithmic certificates) for planar, bounded genus, chordal, interval, circular-arc, permutation and bounded treewidth graphs.

 Vía Zoom. 

Redes Sociales