|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
In this talk, we consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the number of edges, M<E the size of internal memory, and B the block size. The best previous results are sort (E^3/2) I/Os (Dementiev, PhD thesis, 2006) and O(E^2/(MB)) I/Os (Hu et al., SIGMOD 2013), where sort (n) denotes the number of I/Os for sorting n items. We improve the I/O complexity to O(E^3/2/(M B)) expected I/Os, which improves the previous bounds by a factor (E/M,M) . Our algorithm is cache-oblivious and also I/O optimal: We show that any algorithm enumerating t distinct triangles must always use (t/(M B)) I/Os, and there are graphs for which t=(E^3/2) . Finally, we give a deterministic cache-aware algorithm using O(E^3/2/(M B)= I/Os assuming M E^(1) . Our results are based on a new color coding technique, which may be of independent interest. Host: Rolf Fagerberg SDU HOME | IMADA HOME | Previous Page Daniel Merkle |