Zeitkomplexitätsanalyse für den UST-CONN-Algorithmus von Reingold

Was ist die genaue zeitliche Komplexität des ungerichteten Log-Space-Algorithmus für st-Konnektivität von Omer Reingold?

Es scheint, dass die zeitliche Komplexität von Reingolds Algorithmus weder in der Arbeit von Reingold noch im Lehrbuch von Arora-Barak behandelt wird. Es scheint auch, dass die Analyse ziemlich langwierig ist, da die zeitliche Komplexität von dem genauen Expander-Graphen abhängt, der in der Konstruktion verwendet wird, und von einigen Konstanten, die als "ausreichend groß" gewählt werden.

$G$$G'$$l = O(\log n)$$O$$G'$$d = 2^b$$b$$d^l = O(n^c)$$c$$c \ge 10^9b$