This work aims to investigate two logspace algorithms for the undirected connectivity problem. One of them is a randomized algorithm based on the cover time for random walks on graphs, while the other is a deterministic algorithm based on properties of expander graphs and the zig-zag product. Additionally, this work analyzes a probabilistic construction of universal traversal sequences for graphs using an upper bound on the cover time of random walks on graphs. This work provides most of the theoretical background needed to analyze those algorithms and pseudocode implementations for them. In addition, this work addresses several details omitted in the papers that proposed those algorithms.
O objetivo deste trabalho é analisar dois algoritmos com uso de memória logarítmica que resolvem o problema da conexidade em grafos não dirigidos. Um deles é um algoritmo aleatorizado baseado no estudo do tempo de cobertura para passeios aleatórios em grafos, já o outro é um algoritmo determinístico baseado em propriedades de grafos expansores e do produto zig-zag. Além disso, este trabalho examina uma construção probabilística de sequências transversais universais para grafos utilizando uma cota superior para o tempo de cobertura para passeios aleatórios em grafos. Este trabalho provê a maioria dos prerequisitos e resultados básicos necessários para analisar esses algoritmos e implementações em pseudocódigo deles. Além disso, este trabalho considera vários detalhes omitidos nos artigos que propuseram esses algoritmos.