何百万ものノードがあるグラフのドミネーター ツリーを計算するために、Lengauer および Tarjan アルゴリズムとパス圧縮を使用しています。アルゴリズムは非常に複雑であり、完全に理解するのに時間がかかっていないことを認めなければなりません。使用しているだけです。ここで、ルート ノードの直接の子のドミネーター ツリーを計算し、この操作を繰り返して特定の深さまでグラフを再帰する必要があります。つまり、ルート ノードの子のドミネーター ツリーを計算するときに、ルート ノードがグラフから削除されたふりをしたいのです。
私の質問は、ルート ノードの初期ドミネーター ツリーで既に計算されている即時ドミネーター情報を利用する効率的な解決策があるかどうかです。言い換えれば、プロセス全体が非常に時間がかかるため、子供たちのそれぞれについてゼロから始めたくありません。
単純に、グラフの奥深くには、idom が少し上にあり、グラフの上部の変更の影響を受けないノードがたくさんあるため、それは可能であると思われます。
ところで、ドミネーターツリーの主題がコンパイラーの人々によって「所有」されており、古典的なグラフ理論に関する本でそれについて言及されていないのは奇妙です。私が使用しているアプリケーション (私の FindRoots Java ヒープ アナライザー) は、コンパイラ理論とは関係ありません。
明確化: ここでは有向グラフについて話しています。私が参照する「ルート」は、実際には最大の到達可能性を持つノードです。「ツリー」への参照を「グラフ」に置き換えて、上記のテキストを更新しました。形が主に木のような。グラフは実際には Java ヒープ内のオブジェクトであり、ご想像のとおり、適度に階層化されています。OOM リーク分析を行う際にドミネーター ツリーが役立つことが分かりました。答えは最終的にそのドミネーターです。ドミネーター ツリーを使用すると、木ではなく木を<ahem>見ることができます。しかし、時にはたくさんのがらくたが木のてっぺんに浮かぶので、そのすぐ下に何千もの子を持つ根があります。このような場合、ルートの (元のグラフの) 直接の子のそれぞれにルートを持つドミネーター ツリーの計算を試してから、1 つ下のレベルに移動します。（当分の間、バックリンクの可能性について心配しないようにしています:)