bugfix> performance > 投稿

インターネット上には、単一のエントリノードに関してドミネーターツリーを見つけるTarjanのアルゴリズムに関する多くのリソースがあります。ただし、ツリーの単一ノードの支配要素を見つけたいだけです。

これを行う簡単な方法は、ドミネーターツリーを計算し、特定のノードのドミネーターを見つけるためにツリーを反復処理するTarjanのO(m log n)時間アルゴリズムを使用することですか?単一ノードの場合、これをO(m log n)時間よりも早く行いたいです。

回答 1 件
  • 私は何も知りませんが既存の これを行うアルゴリズムは、1つ考えることができます。

    エントリノードをルート、 そしてそのtargetノード(そのドミネーターを見つけるため)t。をルートとするDFSツリーを作成するルート

    ここで、ドミネーターのセットがt の祖先のサブセットですt DFSツリー上で、前方エッジとクロスエッジのみがパス上のノードを「回避」できますルート にt。そう:

    各ノードについてノード、させてf(ノード) の最高の祖先になるt それは達することができますノード 他の祖先を歩くことなくt。これは、メモ化を使用して線形時間で計算できます。

    各クロスエッジについてx→y どこy の祖先ですt、の厳密な後継者であるすべてのノードf(x) との厳密な祖先y の支配者ではないt。 (パスのためルート→...→f(x)→...→x→y→...→t それらのノードを通過しません)

    アルゴリズム(O(n + m)) だろう:

    をルートとするDFSツリーを作成するルート

    すべての祖先をマークするt 「可能な候補」として。

    計算するf(ノード) すべてのノードに対して。

    それぞれについてx→y 上記のように、パス内のノードのリストをマークしますf(x)→...→y (エンドポイントを除く)で「支配者になることはできません」としてO(1) 合計テーブルを使用した時間。<サブ>(合計面積表に似ていますが、1D)

    残りの候補者は支配者です。

    これが簡単かどうかはわかりません。

あなたの答え