5 ms·

I suspect that the algorithm is wrong because the complexity is suspiciously good. https://en.m.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem

I suspect that the algorithm is wrong because the complexity is suspiciously good. https://en.m.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem https://en.m.wikipedia.org/wiki/Triangle-free_graph#Triangle...

deleted 2y ago
[deleted]
vegafrank 2y ago
[dead]
votepaunchy 2y ago
It looks like this algorithm is solving for whether the graph contains at least one triangle rather than counting or listing all triangles.
- vegafrank 2y ago
  [dead]
- deleted 2y ago
  [deleted]
- adrianN 2y ago
  „… which it follows that triangle detection can be solved in time O(m^{1.407})“