Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1997 Copyright 1997 Universität Bonn, Institut für Informatik, Abt. V
85170

Approximate Counting of Given Length Cycles
Carsten Dorgerloh, Juergen Wirtgen
[Download PostScript] [Download PDF]

We present a method for approximate counting simple cycles of a given length in graphs. The main result of this paper is an $(\epsilon,\delta)$-approximation to the number of simple cycles of length $k$ which runs in $\O$$(M(n) \log n/ \epsilon^2 \log (1/\delta))$ time, where $\O$$(M(n))$ is the complexity of matrix multiplication.

Last Change: 11/05/14 at 10:06:34
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope