1313
правок
Полностью динамическая связность: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность (посмотреть исходный код)
Версия от 03:39, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Разработка структуры данных для неориентированного графа с фиксированным | Разработка структуры данных для неориентированного графа с фиксированным множеством вершин, способной обрабатывать запросы вида «Являются ли вершины i и j связанными?» и поддерживать обновления вида «Вставить ребро {i, j}» и «Удалить ребро {i, j}». Задача состоит в минимизации времени выполнения обновления и запроса для наихудшей последовательности запросов и обновлений. Алгоритмы для решения этой задачи называются «полностью динамическими», поскольку, в отличие от «частично динамических» алгоритмов, выполняют как вставку, так и удаление ребер. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 20: | Строка 19: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Можно ли уменьшить время обновления в наихудшем случае до o( | Можно ли уменьшить время обновления в наихудшем случае до <math>o(n^{1/2}) \; </math> при полилогарифмическом времени запроса? | ||
Могут ли нижние границы компромиссов, приведенные в работе [6], быть согласованы для всех возможных вариантов стоимости запросов? | Могут ли нижние границы компромиссов, приведенные в работе [6], быть согласованы для всех возможных вариантов стоимости запросов? | ||
== Применение == | == Применение == | ||
| Строка 31: | Строка 29: | ||
== См. также == | == См. также == | ||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[Полностью | * ''[[Полностью динамический алгоритм транзитивного замыкания]] | ||
== Литература == | == Литература == | ||
| Строка 52: | Строка 49: | ||
9. Zaroliagis, C.D.: Implementations and experimental studies of dynamic graph algorithms. In: Experimental Algorithmics, Dagstuhl seminar, September 2000, Lecture Notes in Computer Science, vol. 2547. Springer (2002), Journal Article: J. Exp. Algorithmics 229–278 (2000) | 9. Zaroliagis, C.D.: Implementations and experimental studies of dynamic graph algorithms. In: Experimental Algorithmics, Dagstuhl seminar, September 2000, Lecture Notes in Computer Science, vol. 2547. Springer (2002), Journal Article: J. Exp. Algorithmics 229–278 (2000) | ||
[[Категория: Совместное определение связанных терминов]] | |||