4446
правок
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Инкрементные алгоритмы на графах; [[полностью динамическ…») |
Irina (обсуждение | вклад) м (→См. также) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Разработка структуры данных для неориентированного графа с фиксированным | Разработка структуры данных для неориентированного графа с фиксированным множеством вершин, способной обрабатывать запросы вида «Являются ли вершины i и j связанными?» и поддерживать обновления вида «Вставить ребро {i, j}» и «Удалить ребро {i, j}». Задача состоит в минимизации времени выполнения обновления и запроса для наихудшей последовательности запросов и обновлений. Алгоритмы для решения этой задачи называются «полностью динамическими», поскольку, в отличие от «частично динамических» алгоритмов, выполняют как вставку, так и удаление ребер. | ||
== Основные результаты == | == Основные результаты == | ||
Холм и коллеги [4] предложили первый детерминированный полностью динамический графовый алгоритм, поддерживающий связность неориентированного графа, с полилогарифмическим амортизированным временем на одну операцию – в частности, с амортизированной стоимостью операции обновления O( | Холм и коллеги [4] предложили первый детерминированный полностью динамический графовый алгоритм, поддерживающий связность неориентированного графа, с полилогарифмическим амортизированным временем на одну операцию – в частности, с амортизированной стоимостью операции обновления <math>O(log^2 \; n)</math> и выполнения запроса <math>O(log \; n / log \; log \; n)</math> в наихудшем случае, где n – количество вершин графа. Базовая техника расширяется для поддержки минимальных остовных деревьев с амортизированной стоимостью одной операции обновления <math>O(log^4 \; n)</math> и 2-реберной связности и двусвязности с амортизированным временем одной операции <math>O(log^5 \; n)</math>. | ||
Алгоритм полагается на простую новую технику поддержки остовного леса в графе, обеспечивающую возможность эффективного поиска ребра замены в случае удаления древесного ребра. Эта техника гарантирует, что каждое недревесное ребро проверяется не более <math>log_2 \; n</math> раз. Алгоритм использует уже известные древесные структуры данных – такие как верхушки деревьев или ET-деревья – для хранения и быстрого извлечения информации об остовных деревьях и инцидентных им недревесных дугах. | |||
Алгоритмы с временем запроса <math>O(log \; n / log \; log\; log \; n)</math> и ожидаемым амортизированным временем обновления <math>O(log \; n (log \; log \; n)^3)</math> в случае связности и с ожидаемым амортизированным временем обновления <math>O(log^3 \; n \; log \; log \; n)</math> в случае 2-реберной связности и двусвязности были предложены в [6]. Нижние границы, демонстрирующие континуум компромиссов в случае связности между временем выполнения обновлений и запросов в модели клеточного зонда, согласованные с известными верхними границами, были доказаны в [5]. Более конкретно, если <math>t_u \;</math> и <math>t_q \; </math> – амортизированное время обновления и запроса, соответственно, то <math>t_q \cdot lg(t_u / t_q) = \Omega(lg \; n)</math> и <math>t_u \cdot lg(t_q / t_u) = \Omega(lg \; n)</math>. | |||
Несколько отличный от них, известный ранее рандомизированный метод вычисления динамической связности с ожидаемым амортизированным временем обновления <math>O(log^3 n) \; </math> был предложен в работе [2] и улучшен до <math>O(log^2 n) \; </math> в [3]. Метод, минимизирующий время обновления в наихудшем случае, а не амортизированное, был предложен в [1]: <math>O( \sqrt{n})</math> на одно обновление для алгоритма связности, а также для 2-реберной связности и двусвязности. | |||
== Открытые вопросы == | == Открытые вопросы == | ||
Можно ли уменьшить время обновления в наихудшем случае до o( | Можно ли уменьшить время обновления в наихудшем случае до <math>o(n^{1/2}) \; </math> при полилогарифмическом времени запроса? | ||
Могут ли нижние границы компромиссов, приведенные в работе [6], быть согласованы для всех возможных вариантов стоимости запросов? | Могут ли нижние границы компромиссов, приведенные в работе [6], быть согласованы для всех возможных вариантов стоимости запросов? | ||
== Применение == | == Применение == | ||
Строка 32: | Строка 29: | ||
== См. также == | == См. также == | ||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[Полностью | * ''[[Полностью динамический алгоритм транзитивного замыкания]] | ||
== Литература == | == Литература == |
правок