Ich suche nach einem schnellen Algorithmus, um den maximalen Fluss in dynamischen Graphen zu berechnen (Hinzufügen / Löschen eines Knotens mit zugehörigen Kanten zum Graphen). d. h. wir haben einen maximalen Fluss in G, jetzt wird ein neuer Knoten hinzugefügt / gelöscht mit verwandten Kanten. Ich möchte den maximalen Fluss für ein neues Diagramm nicht neu berechnen. Tatsächlich möchte ich die vorherigen verfügbaren Ergebnisse für dieses Diagramm verwenden.
Jede Vorverarbeitung, die nicht sehr zeit- / speicherkonsumfähig ist, wird verwendet.
Die einfachste Idee ist es, den Fluss neu zu berechnen.
Eine weitere einfache Idee ist, alle augmentierenden Pfade zu speichern, die in der vorherigen Maxflowberechnung verwendet wurden, jetzt können wir zum Hinzufügen von Vertex v einfache Pfade (im aktualisierten Kapazitätsgraphen nach vorherigem Schritt) finden, die von der Quelle ausgehen, zu gehen v geht dann zum Ziel, aber Problem ist, dass dieser Pfad einfach sein sollte, ich könnte nicht besser als O (n * E) für diesen Fall finden. (Wenn es nur einen Pfad oder Pfade gab, die nicht zusammenhängen, kann dies in O (n + E) gemacht werden, aber es ist nicht so).
Auch zum Entfernen von Knoten oben funktioniert die Idee nicht.
Auch meine Frage bezieht sich nicht auf eine andere Frage, die aussieht an dynamischen Kanten hinzufügen / entfernen .
Ich habe diese Frage in CSTheory.StackExchange gestellt. Zum Hinzufügen eines Knotens, wie ich es mit anderen besprochen habe, ist die Neuberechnung schneller als bei anderen bekannten Algorithmen, da die Neuberechnung auf einem semi-spärlichen Graphen (Restgrafik) ausgeführt wird. Es gab eine gute Antwort, den Knoten (der entfernt werden will) in zwei Mengen, v_in und v_out, und Berechnung des Flusses auf Restgraphen von v_in nach v_out und erneut Berechnung des Flusses im Restgraphen von v_in nach v_out durch Hinzufügen einer unendlichen Kante zwischen der Quelle und Ziel. (und schließlich den Unterschied vergleichen und den Restgraphen aktualisieren). Sie können verwandte Q / A und Diskussionen in Incremental Maximum Flow in dynamischen Diagrammen .
Wenn Sie Vertex v hinzufügen möchten, verwenden Sie den alten Flow f und berechnen Sie das Residuendiagramm und erhalten Sie dann einen Augmentierungsweg nach DFS OutDeg (v).
Um einen Vertex v zu entfernen - berechnen Sie den ganzen Fluss, der v verlässt, sagen wir die Summe des Flusses, der v verlässt, dann während (a & gt; 0) einen Weg P von s nach t findet, der durch v geht, und reduziert f (P) aus der Strömung und aus a.
Ich denke, das sollte helfen ... Ich bin sicherer auf die Zugabe dann auf die Entfernung, so ID Liebe, um in Kommentaren korrigiert werden:)
Zum dynamischen Hinzufügen eines Vertex v und der zugehörigen Kanten E :
1) Fügen Sie v selbst dem Diagramm hinzu. Da es keine Kanten hat, kann es den maximalen Fluss nicht beeinflussen.
2) Fügen Sie die zugehörigen Kanten E nacheinander dem Graphen hinzu, indem Sie den Algorithmus aus diese Frage
Machen Sie das Umgekehrte zum Löschen eines Eckpunkts und der zugehörigen Kanten.