Максимальный поток в динамических графах

Я ищу быстрый алгоритм для вычисления максимального потока в динамических графах (добавление/удаление узла со связанными ребрами с графом). i.e у нас есть максимальный поток в G, теперь новый узел добавлен/удален с связанными ребрами, мне не нравится пересчитывать максимальный поток для нового графика, на самом деле я хочу использовать предыдущие доступные результаты для этого графика.Максимальный поток в динамических графах

Любая предварительная обработка, которая не является потребителем времени/памяти, присваивается.

Простейшая идея - пересчет потока.

Еще одна простой идеи заключается в том, как это, сохранить все увеличивающиеся пути, которые используются при расчете предыдущего MaxFlow, теперь для добавления вершины v, можно найти простые пути (в обновленной мощности графе от предыдущего шага), которые начинаются от источника, идет к v затем идет в пункт назначения, но проблема в том, что этот путь должен быть простым, я не мог найти лучше, чем O (n * E) для этого случая. (если бы это был только один путь или пути были непересекающимися, это можно сделать в O (n + E), но это не так).

Также для удаления узла над идеей не работает.

Также мой вопрос не связан с another question which looks on dynamic edges adding/removing.

источник

2012-01-26 Saeed Amiri

Как ваш вопрос не связан со ссылкой, которую вы дали? Кажется, это место для меня. –

@KeithRandall, мой вопрос заключается в добавлении удаления вершины, но вопрос был о ребрах, на самом деле с одной вершиной вы, вероятно, добавите ребра 'n', поэтому вершинный случай более сложный, чем случай края, например, я могу иметь некоторую интуицию с ребра, но мое лучшее решение для вершин не является хорошим решением. –

@Charles, вы бы описали, почему вы удалили тег max-flow? Я добавил этот тег к SO, потому что он полезен. особенно в поисках. –

Я задал этот вопрос в CSTheory.StackExchange, для добавления узла в Я обсуждал с другими, что обнаружил, что пересчет выполняется быстрее, чем другие известные алгоритмы, поскольку пересчет выполняется на полу разреженном графике (остаточный граф), поэтому он достаточно быстр и для удаления узла, был хороший ответ, разделяющий узел (который хочет быть удален) в два набора, v_in и v_out и вычисляют поток на остаточном графе от v_in до v_out и снова вычисляют поток в остаточном графе от v_in до v_out путем добавления бесконечного края между источником и получателем. (и, наконец, сравнение их разности и обновление остаточного графика). Вы можете увидеть связанные вопросы и обсуждения в Incremental Maximum Flow in Dynamic graphs.

источник

2012-02-25 15:58:45

Для динамического добавления вершины v и связанные с ним края E:

1) Добавить v сам по себе на графике. Поскольку он не имеет ребер, он не может влиять на максимальный поток.

2) Добавить связанные края E на графику, по одному за раз, используя алгоритм из this question

ли обратные для удаления вершины и связанное с ним ребром.

источник

2012-01-27 01:21:36

-1 Вы знаете порядок этого алгоритма? это больше, чем O (E) для каждого ребра, на самом деле это нехорошо (мой собственный алгоритм проще и быстрее). Также это (то, что вы предложили) не охватывает удаление узла. –

Для добавления Vertex v используйте старый поток f и вычислите остаточный график, затем получите дополнительный путь по DFS OutDeg (v) раз.

Для удаления вершины v - вычислить весь поток, покидающий v, скажем, сумма потока, выходящего из v, равна a, тогда while (a> 0) найдите путь P от s до t, который движется в направлении v, и уменьшите f (P) от потока и от a.

я думаю, что должно помочь ... им более уверены в добавлении затем на отдалении, так что идентификатор любит, чтобы исправить в комментариях :)

источник

2012-02-12 00:01:23

Хорошее предложение, но ваш подход к добавлению вершин принимает O (n * E) в худшем случае. Также ваш вариант удаления принимает O (n * E). Также я не думаю, что это правильный путь, но ваш подход к добавлению проще, чем мой. –

Я не думаю, что вы можете сделать что-нибудь лучше, чем тогда ... вы уверены, что есть лучший способ? обратите внимание, что outdeg (v) вряд ли будет таким высоким в большинстве графиков, поэтому его обычный случай должен работать в O (E) ... –

В среднем (со случайными графами) среднее значение не должно быть O (E) будет иметь степень вокруг n/2 для новых вершин. но в настоящее время я думаю, что у вашего алгоритма есть некоторая ошибка. Это не оценка времени использования (v), может быть, нам нужно больше, чем это (в случаях, когда вы пересекаете один новый добавленный край более одного раза). Также я не думаю, что есть прямой алгоритм, но спросите его здесь, чтобы узнать, есть ли у кого-то хорошая идея? –

Максимальный поток в динамических графах

ответ

Смежные вопросы