Análisis de complejidad temporal para el algoritmo UST-CONN de Reingold

¿Cuál es la complejidad de tiempo exacta del algoritmo de espacio de registro de conectividad st no dirigida por Omer Reingold?

Parece que la complejidad temporal del algoritmo de Reingold no se trata ni en el artículo de Reingold ni en el libro de texto de Arora-Barak. También parecería que el análisis es bastante tedioso, ya que la complejidad del tiempo depende del gráfico expansor exacto utilizado en la construcción y de algunas constantes que se eligen como "suficientemente grandes".

Para tener una idea aproximada de la complejidad del tiempo, observe que el algoritmo de Reingold, dado el gráfico , lo transforma (implícitamente) en un gráfico expansor y atraviesa cada paso de longitud . La notación oculta algunas constantes bastante grandes aquí. El gráfico tiene un grado constante de para algunos suficientemente grande , lo que significa que hay tales paseos para alguna constante bastante grande . Deslizando algunas notas de clase sobre el tema, parece que .$G$$G'$$l = O(\log n)$$O$$G'$$d = 2^b$$b$$d^l = O(n^c)$$c$$c \ge 10^9b$