Анализ сложности времени для алгоритма Рейнгольда UST-CONN

Какова точная временная сложность неориентированного алгоритма пространства журналирования st-связности Омера Рейнгольда?

Кажется, что временная сложность алгоритма Рейнгольда не рассматривается ни в статье Рейнгольда, ни в учебнике Арора-Барака. Также может показаться, что анализ довольно утомителен, поскольку сложность времени зависит от точного графа расширителя, используемого в конструкции, и от некоторых констант, выбранных как «достаточно большие».

Чтобы получить некоторое приблизительное представление о сложности времени, обратите внимание, что алгоритм Рейнгольда, учитывая граф , преобразует его (неявно) в граф экспандера и пересекает каждый шаг длины . В -notation скрывает некоторые довольно большие постоянные здесь. Граф имеет постоянную степень для некоторого достаточно большого , что означает, что существуют такие прогулки для некоторой довольно большой постоянной . Считая некоторые лекционные заметки на эту тему, можно подумать, что .$G$$G'$$l = O(\log n)$$O$$G'$$d = 2^b$$b$$d^l = O(n^c)$$c$$c \ge 10^9b$