Título: Random walk based algorithms for generating uniform spanning trees

Palestrante: Giulio Iacobelli (IM-UFRJ)
Organizadores: Guilherme Ost e Maria Eulalia Vares
Data: 14/12/2020
Horario: 15:00.a 16:00 (Rio de Janeiro local time)
Local: Transmissão online

Confira AQUI o link para a transmissão.

Resumo: The task of efficiently generating uniform spanning trees of a graph has received much attention. A breakthrough came with Aldous-Broder and Wilson's algorithms, which can efficiently generate spanning trees based on random walks. In this work, we study the transient behavior of both algorithms. We introduce the notion of branches, which are paths generated by the two algorithms on particular stopping times. This interpretation is used to show a transient equivalence between the two algorithms on complete graphs. This equivalence yields a hybrid approach to generate uniform spanning trees of complete graphs faster than either of the two algorithms. We also propose a two-stage framework to explore this hybrid approach beyond complete graphs, showing its feasibility in some examples.

All the talks are held in English.