Максимальный поток в динамических графиках
Я ищу быстрый алгоритм для вычисления максимального потока в динамических графах (добавление / удаление узла со связанными ребрами к графу). т.е. у нас есть максимальный поток в G, теперь новый узел добавлен / удален со связанными ребрами, я не люблю пересчитывать максимальный поток для нового графа, на самом деле, я хочу использовать предыдущие доступные результаты для этого графа.
Любая предварительная обработка, которая не очень потребляет время / память, присваивается.
Простейшая идея - пересчитать поток.
Другая простая идея заключается в следующем: сохранить все пути расширения, которые использовались в предыдущем вычислении максимального потока, теперь для добавления вершины. v, мы можем найти простые пути (в обновленном графике производительности на предыдущем шаге), которые начинаются с источника, идет к v затем идет к месту назначения, но проблема в том, что этот путь должен быть простым, я не мог найти лучше, чем O(n*E) для этого случая. (если это был только один путь или пути были непересекающимися, это можно сделать в O(n+E), но это не так).
Также для удаления узла выше идея не работает.
Также мой вопрос не связан с другим вопросом, который касается добавления / удаления динамических ребер.
3 ответа
Я задал этот вопрос в CSTheory.StackExchange. Для добавления узла, как я обсуждал с другими, я обнаружил, что пересчет выполняется быстрее, чем другие известные алгоритмы, потому что перерасчет выполняется на полугерметичном графе (остаточном графе), поэтому он достаточно быстр для удаления узла. хороший ответ, разделив узел (который нужно удалить) на два набора, v_in и v_out и вычисляя поток на остаточном графе от v_in до v_out, и снова вычисляя поток в остаточном графе от v_in до v_out, добавляя бесконечный край между источником и назначением. (и, наконец, сравнение их разности и обновление остаточного графика). Вы можете увидеть соответствующие вопросы и ответы в разделе " Максимальный прирост потока" на динамических графиках.
Для добавления вершины v используйте старый поток f и вычислите остаточный граф, затем получите путь дополнения по времени DFS OutDeg(v).
Для удаления вершины v - вычислите весь поток, покидающий v, скажем, что сумма потока, покидающего v, равна a, тогда, пока (a>0) найдите путь P от s до t, который идет через v, и уменьшите f(P) из потока и из.
я думаю, что это должно помочь... я более уверен в добавлении, чем в удалении, так что я люблю исправляться в комментариях:)
Для динамического добавления вершины v и связанные с ним края E:
1) Добавить v сам по себе на графике. Поскольку он не имеет ребер, он не может влиять на максимальный поток.
2) Добавьте связанные ребра E на график, по одному, используя алгоритм из этого вопроса
Сделайте обратное для удаления вершины и связанных с ней ребер.