Полностью динамическая связность: различия между версиями

Алгоритмы с временем запроса <math>O(log \; n / log \; log\;  log \; n)</math> и ожидаемым амортизированным временем обновления <math>O(log \; n (log \; log \; n)^3)</math> в случае связности и с ожидаемым амортизированным временем обновления <math>O(log^3 \; n \; log \; log \; n)</math> в случае 2-реберной связности и двусвязности были предложены в [6]. Нижние границы, демонстрирующие континуум компромиссов в случае связности между временем выполнения обновлений и запросов в модели клеточного зонда, согласованные с известными верхними границами, были доказаны в [5]. Более конкретно, если <math>t_u \;</math> и <math>t_q \; </math> – амортизированное время обновления и запроса, соответственно, то <math>t_q \cdot lg(t_u / t_q) = \Omega(lg \; n)</math> и <math>t_u \cdot lg(t_q / t_u) = \Omega(lg \; n)</math>.

Несколько отличный от них, известный ранее рандомизированный метод вычисления динамической связности с ожидаемым амортизированным временем обновления <math>O(log^3 n) \; </math> был предложен в работе [2] и улучшен до <math>O(log^2 n) \; </math> в [3]. Метод, минимизирующий время обновления в наихудшем случае, а не амортизированное, был предложен в [1]: <math>O( \sqrt{n})</math> на одно обновление для алгоритма связности, а также для 2-реберной связности и двусвязности.