Finding four-node subgraphs in triangle time
Virginia Vassilevska Williams, Joshua R. Wang, Ryan Williams, Huacheng Yu · Symposium on Discrete Algorithms · 2015
We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i.e., a triangle).• The best known algorithms for triangle finding in an n-node graph take O(nω) time, where ω