Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study

By Thomas Schank, D. Wagner. Workshop on Engineering Applications, 2005

337 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Efficient semi-streaming algorithms for local triangle counting in massive graphs (2008, methodology): “A description and an experimental evaluation of those “iterator” algorithms can be found in [30]; however, their running time is O(|V |d(2)max) and O( P v∈V d 2 v), respectively.”
Main-memory triangle computations for very large (sparse (power-law)) graphs (2008, methodology): “Lemma 3 ([24, 33, 34]) Listing all triangles in G is in Ω(n3) and Ω(m 3 2 ) time.”
EmptyHeaded: A Relational Engine for Graph Processing (2015, methodology): “EmptyHeaded supports block sizes that are powers of two with a default of 256.5 As shown, we pack the offsets contiguously, which allows us to regard the offsets as a uint layout; in turn, this allows EmptyHeaded to use the same algorithm to intersect the offsets as it does for the uint layout.”