English

# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Detecting Directed 4-cycles Still Faster

##### MPS-Authors
/persons/resource/persons44373

Eisenbrand,  Friedrich
Discrete Optimization, MPI for Informatics, Max Planck Society;

/persons/resource/persons44519

Grandoni,  Fabrizio
Discrete Optimization, MPI for Informatics, Max Planck Society;

##### External Ressource
No external resources are shared
##### Fulltext (public)
There are no public fulltexts stored in PuRe
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Eisenbrand, F., & Grandoni, F. (2003). Detecting Directed 4-cycles Still Faster. Information Processing Letters, 87, 13-15.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2CB8-3
##### Abstract
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$.