11:00
12:00

GT AlgoDist, «Universal Exploration Sequences and Undirected s-t Connectivity», Sébastien Bouchard

Sébastien Bouchard

Title: Universal Exploration Sequences and Undirected s-t Connectivity

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 present USTCON, UXS, and provide a high-level view of Reingold's algorithm and its use to construct UXS.

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

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