Используются ли когда-либо деревья с вырезанными ссылками на практике, для вычисления максимального потока или других приложений?

20

Многие алгоритмы максимального потока, которые я обычно вижу реализованными, алгоритм Dinic, push relbel и другие, могут улучшить свои асимптотические временные затраты за счет использования динамических деревьев (также известных как деревья среза ссылок).

Push-релабель запускается в или или нормально, но с динамическими деревьями $O(V^2E)$ $O(V^3)$ $O(V^2\sqrt{E})$ $O(VE \log(V^2/E))$
Алгоритм Диника работает в , но с динамическими деревьями $O(V^2E)$ $O(VE\log(V))$

Однако практические реализации алгоритмов максимального потока в большинстве библиотек, похоже, не используют эту структуру данных. Используются ли когда-либо динамические деревья на практике для вычисления максимального потока? Или они несут слишком много накладных расходов, чтобы быть полезными для реальных проблемных размеров?

Есть ли другие проблемные домены, в которых используются деревья ссылок?

Этот вопрос связан с вопросом, который я задал в рамках теории: практичен ли какой-либо из современных алгоритмов максимального потока?

reference-request graphs data-structures network-flow Роб Лахлан
источник

обзор / описание деревьев разреза ссылок, но только состояния "полезно для таких приложений, как Network Flow"

vzn

из опроса тарьян, цитируемого Резой, в основном алгоритмы линейного времени работают очень хорошо / лучше всего для умеренного числа вершин / ребер, а затем есть порог больших вершин / ребер, где логарифмические алгоритмы превосходят линейный алгоритм. поэтому логарифмический доступ fns полезен и может быть значительно лучше для очень больших графиков.

vzn

7

Существует статья под названием « Динамические деревья на практике », в которой рассматривается практическая реализация.

Другие категории, которые дерево Link-Cut могло бы эффективно использовать, находятся в индексировании базы данных . Вы можете найти это в книге « Методы индексирования базы данных ».

Реза
источник

думаю, что это требует некоторой проработки. Конечно, деревья полезны для индексов, но при каких условиях дерево будет модифицировано?

vzn

@vzn: B + -дерево, R-дерево, H-дерево и X-дерево - некоторые примеры.

Реза

конечно, но подозреваю, что, возможно, до сих пор никто не пытался использовать деревья ссылок в индексах БД. Это правдоподобное приложение, но кажется неясным, что они оптимизированы для тех же операций, которые происходят в индексах БД.

vzn

5

В конце этой статьи выясняется, что дерево среза ссылок (LC) превосходит деревья с граблями (RC) для алгоритма максимального потока Sleator / Tarjan, используя стандартный генератор случайных графов Dimacs.

В статье рассматривается распространение изменений как одно из приложений динамических деревьев. например, распространение изменений аналогично тому, как нужно пересчитывать ячейки электронной таблицы Excel на основе изменений в некоторых ячейках на основе зависимостей ячейки / формулы. авторы выпустили свой код в виде открытой библиотеки.

Экспериментальный анализ распространения изменений в динамических деревьях Acar, Blelloch, Vittes

Распространение изменений - это метод для автоматической настройки выходных данных алгоритма в соответствии с изменениями входных данных. Идея, лежащая в основе распространения изменений, заключается в отслеживании зависимостей между вызовами данных и функций, чтобы при изменении входных данных функции, затронутые этим изменением, могли быть повторно выполнены для обновления вычислений и выходных данных. Распространение изменений позволяет компилятору динамизировать статические алгоритмы.

ВЗН
источник

Спасибо. Приятно видеть некоторые тесты алгоритмов с участием динамических деревьев.

Роб Лахлан

Используются ли когда-либо деревья с вырезанными ссылками на практике, для вычисления максимального потока или других приложений?

Ответы: