11:00
12:00

Sébastien Bouchard

Title: Universal Exploration Sequences and Undirected s-t Connectivity (continued)

Abstract:

Undirected s-t connectivity (USTCON) is a SL-complete problem (SL stands for Symmetric Log-space). During decades, researchers tried to propose a log-space algorithm for this problem. It would prove that SL=L. This was achieved in 2005 by Omer Reingold. His USTCON algorithm can also be used to construct sequences of integers called universal exploration sequences (UXS) which, given the number of vertices of a graph, can guide a deterministic walk, of polynomial length, allowing to visit all its nodes.

The talk will provide a high-level view of Reingold's algorithm use to construct UXS, as a continuation of the previous talk.

https://algodist.labri.fr/index.php/Main/GT

LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp