アイテム詳細

要旨

We present a method to detect simple cycles of length~4 of a directed graph in~$O(n^{1/\omega} e^{2-2/\omega})$ steps, where $n$~denotes the number of nodes, $e$ denotes the number of edges and $\omega$ is the exponent of matrix multiplication. This improves upon the currently fastest methods for $\alpha\in (2/(4-\omega),(\omega+1)/2)$, where $e=n^\alpha$.