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.
Official Website: http://dx.doi.org/10.1016/S0020-0190(03)00252-7
Abstract
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α.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Uncontrolled Keywords: | Algorithms; Directed 4-cycle; Computational complexity |
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 15:20 |
| Last Modified: | 24 May 2016 06:22 |
| URI: | http://repository.supsi.ch/id/eprint/4538 |
Actions (login required)
 |
View Item |