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

Question

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

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

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

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

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

Также мой вопрос не связан с другим вопросом, который касается динамических ребер, добавляя / удаляя .

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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