Compact local certification of graph classes

22 Jun

Pedro Montealegre, Associate Professor in Universidad Adolfo Ibáñez, Santiago (Chile)

External Presentation (External Speaker)

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

More info

You can also follow this seminar online:

  • Location: MR-A1 [Ramón] & MR-A2 [Cajal], IMDEA Networks Institute, Avda. del Mar Mediterráneo 22, 28918 Leganés – Madrid
  • Organization: NETCOM Research Group (Telematics Engineering Department, UC3M); IMDEA Networks Institute
  • Time: 12:00
  • Add to Calendar: iCalendar Outlook Google