4551
правка
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
м
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:17, 15 июня 2018
, 15 июня 2018→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
'''Теорема 1 (Хензингер и Кинг [6], 1995). Пусть дан ориентированный граф общего вида. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время <math>O(n / log \; n)</math> в наихудшем случае и операции обновления – за амортизированное время <math>O(m \sqrt{n} log^2 \; n)</math>.''' | '''Теорема 1 (Хензингер и Кинг [6], 1995). Пусть дан ориентированный граф общего вида. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время <math>O(n / log \; n)</math> в наихудшем случае и операции обновления – за амортизированное время <math>O(m \sqrt{n} \; log^2 \; n)</math>.''' | ||
| Строка 59: | Строка 59: | ||
'''Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время <math>O(n^{\epsilon})</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>.''' | ||