10

動的グラフの最大フローを計算するための高速アルゴリズムを探しています（グラフに関連するエッジを持つノードを追加/削除）。つまり、Gに最大フローがあり、関連するエッジで新しいノードが追加/削除されました。新しいグラフの最大フローを再計算するのは好きではありません。実際、このグラフには以前に利用可能な結果を​​使用したいと思います。

時間/メモリの消費量が少ない前処理が適切に使用されます。

最も簡単なアイデアは、フローを再計算することです。

もう1つの簡単なアイデアは、これまでのmaxflow計算で使用したすべての拡張パスを保存し、頂点を追加するために、ソースから開始して宛先に移動するv単純なパス（前のステップで更新された容量グラフ）を見つけることができますが、v問題は、このパスは単純である必要があることです。この場合、O（n * E）よりも優れたものを見つけることができませんでした。（それが1つのパスであるか、パスが互いに素である場合、これはO（n + E）で実行できますが、そうではありません）。

また、上記のノードを削除するためのアイデアは機能しません。

また、私の質問は、動的エッジの追加/削除を調べる別の質問とは関係ありません。

4

3 に答える 3

1

頂点vを追加するには、古いフローfを使用して残余グラフを計算し、DFS OutDeg（v）回で拡張パスを取得します。

頂点vを削除するために-vを離れるすべてのフローを計算します。たとえば、vを離れるフローの合計がaであるとすると、（a> 0）sからtへのパスPを見つけて、f（P ）フローからおよびaから。

私はそれが役立つはずだと思います...削除よりも追加の方が確実なので、コメントで修正するのが大好きです:)

于 2012-02-12T00:01:23.843 に答える
0

v頂点とそれに関連するエッジを動的に追加するにはE：

v1）グラフに単独で追加します。エッジがないため、最大フローに影響を与えることはありません。

2）この質問Eのアルゴリズムを使用して、関連するエッジを一度に1つずつグラフに追加します

頂点とそれに関連するエッジを削除するには、逆の操作を行います。

于 2012-01-27T01:21:36.593 に答える
0

CSTheory.StackExchangeでこの質問をしました。他の人と話し合ったようにノードを追加する場合、再計算は他の既知のアルゴリズムよりも高速であることがわかりました。再計算はセミスパースグラフ（残差グラフ）で実行されるため、ノードを削除するのにも十分な速度であるため、良い答えは、ノード（削除したい）をv_inとv_outの2つのセットに分割し、v_inからv_outまでの残差グラフのフローを計算し、ソースと宛先の間に無限のエッジを追加して、v_inからv_outまでの残差グラフのフローを再度計算することです。（そして最後にそれらの違いを比較し、残差グラフを更新します）。関連するQ/Aと説明は 、動的グラフの増分最大フローで確認できます。

于 2012-02-25T15:58:45.887 に答える