4430
правок
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
м
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:14, 15 июня 2018
, 15 июня 2018нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 10: | Строка 10: | ||
insert(u, v): вставка дуги (u, v) в граф; | insert(u, v): вставка дуги (u, v) в граф; | ||
delete(u, v): удаление дуги (u ,v) из графа; | delete(u, v): удаление дуги (u, v) из графа; | ||
query(..): ответ на запрос о выполнении свойства P графа. | query(..): ответ на запрос о выполнении свойства P графа. | ||
| Строка 28: | Строка 28: | ||
insert(u, v): вставка дуги (u, v) в граф; | insert(u, v): вставка дуги (u, v) в граф; | ||
delete(u, v): удаление дуги (u ,v) из графа; | delete(u, v): удаление дуги (u, v) из графа; | ||
query(x, y): возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае. | query(x, y): возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае. | ||
| Строка 37: | Строка 37: | ||
insert(u, v, w): вставка дуги (u, v) с весом w в граф; | insert(u, v, w): вставка дуги (u, v) с весом w в граф; | ||
delete(u, v): удаление дуги (u ,v) из графа; | delete(u, v): удаление дуги (u, v) из графа; | ||
query(x, y): возвращает расстояние между x и y в графе либо значение +1 в случае, если не существует ориентированного пути из x в y. | query(x, y): возвращает расстояние между x и y в графе либо значение +1 в случае, если не существует ориентированного пути из x в y. | ||
| Строка 53: | Строка 53: | ||
Теорема 1 (Хензингер и Кинг [6], 1995). Пусть дан ориентированный граф общего вида. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n/ log n) в наихудшем случае и операции обновления – за амортизированное время O(m | '''Теорема 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 вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O( | '''Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время <math>O(n^{\epsilon})</math> и операции вставки и удаления – за время о(и'°'1'е'1' е + n1+€) для любого e 2 [0;1], где <w(l,e, 1) – показатель степени при умножении матрицы n x n€ на матрицу n€ x n.''' | ||