3 ms·

Aegypti: Faster Triangle Finding and More

• vegafrank 2y ago
  [dead]
• adrianN 2y ago
  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})“
• vegafrank 2y ago
  [dead]
• vegafrank 2y ago
  [dead]
• vegafrank 2y ago
  [dead]
• deleted 2y ago
  [deleted]
• vegafrank 2y ago
  [dead]
• vegafrank 2y ago
  [dead]