Grad Student, Department of Computer Science

3/16/2004

3:30pm-4:30pm

For fixed *k* we present linear and almost-linear time algorithms to
find a directed cycle of length >= *k*, if one exists. We find a
directed cycle of length >= *log n / log log n* in polynomial time,
if one exists. Under an appropriate complexity assumption it is known to be
impossible to improve this by more than a *log log n* factor. Our
approach is based on depth-first search.

Department of Computer Science

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu