グラフ内のすべての2ホップネイバーリストを見つけるアルゴリズム

Question

グラフが与えられた$ g =（v、e）$、ここで$ | v | = n $。 $ v $のすべてのノードのすべての2ホップ近隣リストのコレクションを生成するための高速アルゴリズムは何ですか。

素朴に、$ o（n^3）$でそれを行うことができます。マトリックスのパワーを使用すると、Strassenアルゴリズムを使用して$ o（n^{2.8}）$でそれを行うことができます。別のマトリックス乗算アルゴリズムを使用して、これよりもうまくできます。より良い方法はありますか？ラスベガスアルゴリズムはありますか？

Answer 1

質問は、実際には2ホップの正確な定義は何ですか。 2ホップでは、set $$ hp（v）= {u mid mbox {uとv} }の間に長さ2のパスがある場合、$$がある場合、現在の答えはノーです。 $ o（n^{ omega}）$よりも速くすることはできません。ここで、$ omega $は、マトリックス製品の実行の複雑さに関連する通常の定数です。

なんで？ vertex $ v $すべての場合、$ v $が$ hp（v）の頂点に隣接しているかどうかを確認します。$もしそうな場合、グラフに三角形が見つかりました。さらに、このプロパティとvertex $ v $が見つからない場合、グラフは三角形のないものです。

グラフが三角形である場合にテストするための現在最もよく知られているアルゴリズムには、時間の複雑さ$ o（n^{ omega}）。$があります。