216. Informatik-Kolloquium

Gastvortrag (Professur Theoretische Informatik und Informationssicherheit)

Prof. Dr. Carlos Hoppen

Universidade Federal do Rio Grande do Sul,
Porte Alegre, Brasilien
 

"Random regular graphs, large girth and local algorithms"

Mittwoch, 23.10.2013
11:30 Uhr, Straße der Nationen 62, 1/375

Alle interessierten Personen sind herzlich eingeladen!

Abstract:

I shall talk about properties of regular graphs with large girth which may be obtained by studying certain algorithms and showing a relationship between their behaviour on random regular graphs and their behaviour on regular graphs of large girth. More precisely, we make use of existing algorithms for fi nding large substructures in random regular graphs, and a powerful way of analysing them, to obtain information about the performance of a class of iterative randomised algorithms. Our results can be viewed as a partial converse of results which translate properties of regular graphs of large girth into properties of random regular graphs. This is joint work with Nick Wormald (Monash University, Australia)