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.

About Pedro Montealegre

Pedro Montealegre is an Associate Professor in the Engineering and Sciences Faculty at Universidad Adolfo Ibáñez in Santiago, Chile. He has an engineering degree with a major in mathematics from Universidad de Chile, later received his Ph.D. in Computer Science from the University of Orléans, and was a postdoctoral fellow at Universidad Adolfo Ibáñez. His research is mainly focused on distributed graph algorithms and the complexity of automata networks.

This event will be conducted in English