algorithm - 无向图中的三角形计数

Question

我在一次采访中被问到这个问题，并被告知 O(n^2) 是可能的。任何人都有一个简单的方法吗？

在这里找到一篇论文，告诉我它和矩阵乘法一样难：http: //kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

Answer 1

http://en.wikipedia.org/wiki/Triangle-free_graph

测试一个图是否是无三角形的将通过该问题的解决方案来解决。从面试官的角度来看，O(n^2) 应该是一个错误。

Answer 2

已证明三角形列表算法的下限为 O(n^3) 或 O(m^1.5)，这里 n 是顶点数，m 是边数。如果你想用矩阵乘法解决三角形计数，时间复杂度与矩阵乘法相同。

你应该列出你的问题的更多细节。也许图有一些特殊的属性。