home · mobile · calendar · bactac · 2003-2004 · 

BACTAC - Nie

Finding a Long Directed Cycle
Shuxin Nie
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
www.cs.colorado.edu
May 5, 2012 (14:24)
XHTML 1.0/CSS2
©2012