English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

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$.