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

== Ключевые слова и синонимы ==

[[Полностью динамическая реберная связность]]; [[полностью динамическая вершинная связность]]

== Постановка задачи ==

3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4.

== Применение ==

Задачи вершинной и реберной связности часто возникают в вопросах, связанных с надежностью и живучестью сетей. В компьютерных сетях вершинная связность графов, лежащих в их основе, соответствует наименьшему числу узлов, падение которых еще не приведет к потере связности всей сети. Подобным же образом, реберная связность графов соответствует наименьшему числу связей, падение которых еще не вызовет потери связности всей сети. Аналогично, если две вершины являются k-вершинно-связными, они останутся связанными даже при отказе до (k – 1) других вершин, а если они являются k-реберно-связными, они «переживут» отказ до (k – 1) связей. Важно изучать динамические версии этих задач в контекстах, где сети динамически меняются – например, в случаях, когда связи могут нарушаться и восстанавливаться из-за отказов и ремонтов.

   

== Открытые вопросы ==

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

== См. также ==

* ''[[Полностью динамическая проверка на планарность]]

* ''[[Полностью динамическое транзитивное замыкание]]

== Литература ==