Complexity of counting cycles using zeons

摘要

Nilpotent adjacency matrix methods are employed to count k-cycles in simple graphs on n vertices for any k≤ n. The worst-case time complexity of counting k-cycles in an n-vertex simple graph is shown to be  (n~(x+1)2~n), where α ≤ 3 is the exponent representing the complexity of matrix multiplication. When k is fixed, the counting of all fc-cycles in an n-vertex graph is of time complexity O(n~(α+k-1)). Letting Ω = (~n_2), the average-case time complexity of counting fc-cycles in an n-vertex, e-edge graph where e < q (~Ω_k-1) for fixed 0 < q < 1 is found to be O(n~4(1 + q)~n). The storage complexity of the approach detailed herein is O(n~2 2~n). For reference, experimental results detailing computation times (in seconds) are included alongside similar computations performed with algorithms based on the approaches of Bax and Tarjan.