Detecting directed 4-cycles still faster

Eisenbrand, Friedrich and Grandoni, Fabrizio (2003) Detecting directed 4-cycles still faster. Information Processing Letters, 87 (1). pp. 13-15. ISSN 0020-0190

Full text not available from this repository.


We present a method to detect simple cycles of length 4 of a directed graph in O(n1/ωe2−2/ω) steps, where n denotes the number of nodes, e denotes the number of edges and ω is the exponent of matrix multiplication. This improves upon the currently fastest methods for α∈(2/(4−ω),(ω+1)/2), where e=nα.

Actions (login required)

View Item View Item