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

Эпстайн и коллеги [], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при <math>k \ge 5 \; </math> эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических.  Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности.