Finding Small Complete Subgraphs Efficiently
(I) We revisit the algorithmic problem of finding all triangles in a graph G= (V, E) with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in O(mα) = O(m3 / 2) time, where α= α(G) is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that
