修正されたborůvkaのアルゴリズムのより緊密な分析

Question

borůvkaのアルゴリズム グラフ$ g =（v、e）$の最小スパニングツリーを計算するための標準アルゴリズムの1つであり、$ | v | = n、| e | = m $。

擬似コードは次のとおりです。

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

アウターループの各反復をラウンドと呼びます。各ラウンドでは、内側のループは少なくとも半分でコンポーネントの数を削減します。したがって、せいぜい$ o（ log n）$ラウンドがあります。各ラウンドでは、内側のループは各エッジを最大2回（各コンポーネントから1回）見ます。したがって、実行時間は最大で$ o（m log n）$です。

これで、各ラウンドの後、同じコンポーネント内の頂点のみを接続するすべてのエッジを削除し、コンポーネント間の重複エッジを削除して、内側のループが最小重量エッジであるいくつかのエッジM '<mのみを見るようにします。以前に切断された2つのコンポーネントを接続します。

この最適化は実行時間にどのように影響しますか？

各ラウンドで何らかの形でエッジの数を半分に削減することを知っていれば、実行時間は大幅に改善されます：$ t（m）= t（m /2） + o（m）= o（m） $。

ただし、最適化により、調査されたエッジの数が劇的に減少しますが（最終ラウンドごとに1つのエッジのみ、およびせいぜいコンポーネントが一般的に2を選択します）、この事実をどのように使用して分析を締めることができるかは明らかではありません。実行時の。

Answer 1

頂点の数を半分にしていても、borůvkaのステップが各ステップのエッジの数を半分にしない一般的なグラフのテストケースを作成することができます。興味深いメモは、あなたが提案する最適化は平面グラフで機能することです。これは、平面グラフの場合$ | e | leq 3*| v | -6 $ i、e $ | e | = o（| v |）$。一般的に、グラフのマイナーな閉鎖ファミリのクラスのスピードアップにつながります。

参照：

• マスターズ論文、クロード・アンダーソン（100ページに、Borůvkaのアルゴリズムの最悪のケース入力が記載されています）。 リンク

• 「マイナークローズグラフクラスのMSTの2つの線形時間アルゴリズム」。 Archivum Mathematicum 40（3）：315–320、2004。 リンク