1313
правок
Полностью динамическая связность высоких степеней: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность высоких степеней (посмотреть исходный код)
Версия от 12:14, 25 ноября 2024
, 25 ноября 2024→Литература
Irina (обсуждение | вклад) мНет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
'''Полностью динамическая связность высоких степеней''' --- ''Fully Dynamic Higher Connectivity'' | |||
Полностью динамическая реберная связность (''Fully dynamic edge connectivity''); полностью динамическая вершинная связность (''Fully dynamic vertex connectivity'') | |||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 74: | Строка 76: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Эпстайн и коллеги [3], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при <math>k \ge 5 \; </math> эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических. Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности. | |||
== См. также == | == См. также == | ||
| Строка 83: | Строка 85: | ||
* ''[[Полностью динамические минимальные остовные деревья]] | * ''[[Полностью динамические минимальные остовные деревья]] | ||
* ''[[Полностью динамическая проверка на планарность]] | * ''[[Полностью динамическая проверка на планарность]] | ||
* ''[[Полностью | * ''[[Полностью динамический алгоритм транзитивного замыкания]] | ||
== Литература == | == Литература == | ||
| Строка 121: | Строка 123: | ||
18. Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464 (1992) | 18. Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464 (1992) | ||
[[Категория: Совместное определение связанных терминов]] | |||