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

Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления o(log n) и временем выполнения одного запроса O(poly(log n))? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений.

Наконец, возможно ли разработать алгоритм с совпадающими границами для обновлений и запросов O(log n) для графов общего вида? Заметим, что это возможно для специального случая планарных графов [5].