
University of Bonn > Department of Computer Science > Chair V  
CSReports 1997  Copyright 1997 University of Bonn, Department of Computer Science, 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 