4551
правка
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
м
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:36, 15 июня 2018
, 15 июня 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 72: | Строка 72: | ||
'''Теорема 3 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n) и операции вставки и удаления – за время <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>.''' | '''Теорема 3 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n) и операции вставки и удаления – за время <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>.''' | ||
'''Следствие 1 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время <math>O(n^{0,575}) \;</math>:, а операции вставки и удаления – за время <math>O(n^{1,575}) \;</math>.''' | |||