算法在图中查找所有2跳邻居列表

Question

给定图形$ g =（v，e）$，其中$ | v | = n $。什么是一种快速算法，用于生成$ v $中所有节点的所有2跳社区列表的集合。

天真，您可以在$ O（n^3）$中做到这一点。借助矩阵的功率，您可以使用Strassen算法使用$ O（n^{2.8}）$做到这一点。您可以使用其他矩阵乘法算法做得更好。有更好的方法吗？是否有拉斯维加斯算法？

Answer 1

这个问题实际上取决于2跳的确切定义是什么。如果是2个搭乘，则表示您的意思是$$ hp（v）= {u mid mbox {u和v} }之间有长度2的路径，$$，那么当前的答案是否，您不能比$ o（n^{ omega}）$更快地做到这一点，其中$ omega $是与执行矩阵产品的复杂性相关的通常常数。

为什么？对于每个顶点$ v $检查，如果$ v $在$ hp（v）中与顶点相邻。$如果是这种情况，则您在图中找到了三角形。此外，如果您没有找到此属性的顶点$ v $，则该图是免费的。

目前最著名的测试算法，如果图形为三角形，则具有时间复杂性$ o（n^{ omega}）。$