4551
правка
Компромиссы при решении динамических графовых задач: различия между версиями
Материал из WEGA
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:29, 15 июня 2018
, 15 июня 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 60: | Строка 60: | ||
'''Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время <math>O(n^{\epsilon})</math> и операции вставки и удаления – за время <math>O(n^{\omega(1, \epsilon, 1) - \epsilon} + n^{1 + \epsilon})</math> для любого <math>\epsilon \in [0, 1] \;</math>, где <math>\omega(1, \epsilon, 1) \;</math> – показатель степени при умножении матрицы <math>n \times n^{\epsilon}</math> на матрицу <math>n^{\epsilon} \times n</math>.''' | '''Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время <math>O(n^{\epsilon})</math> и операции вставки и удаления – за время <math>O(n^{\omega(1, \epsilon, 1) - \epsilon} + n^{1 + \epsilon})</math> для любого <math>\epsilon \in [0, 1] \;</math>, где <math>\omega(1, \epsilon, 1) \;</math> – показатель степени при умножении матрицы <math>n \times n^{\epsilon}</math> на матрицу <math>n^{\epsilon} \times n</math>.''' | ||
Заметим, что зависимость границ от параметра <math>\epsilon \;</math> обеспечивает весь диапазон выбора компромиссов между временем запроса и обновления. Для сбалансированного сочетания двух термов в границе обновления теоремы 2 необходимо, чтобы <math>\epsilon \;</math> удовлетворяло равенству <math>\omega(1, \epsilon, 1) = 1 + 2 \epsilon \;</math>. Из наилучшей известной границы на <math>\omega(1, \epsilon, 1) \;</math> [2, 7] следует, что <math>\epsilon < 0,575 \;</math>. Таким образом, наименьшее время обновления составляет <math>O(n^{1,575}) \;</math>, из чего следует время запроса <math>O(n^{0,575}) \;</math>: | |||
Следствие 1 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время O(n0,575), а операции вставки и удаления – за время O(n1,575). | |||
Санковски обобщил этот результат на случай ориентированных графов общего вида [13]: | |||
Теорема 3 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n€) для любого O)(l,€,!)-€ + n и операции вставки и удаления – за время O(n £ 2 [0;1], где <w(l,e, 1) – показатель степени при умножении матрицы n x n€ на матрицу n€ x n. | |||
