home · mobile · calendar · colloquia · 1999-2000 · 

Colloquium - Gabow

How to Do Depth-first Search?
Department of Computer Science, University of Colorado

Depth-first search is the basis of most algorithms for fundamental graph properties. We propose that depth-first search should be conceptualized according to the natural intuitive view. This is not how DFS is currently taught and it is not how previous DFS algorithms work. To support the proposal we describe an efficient DFS algorithm for finding strong components. There are similar algorithms for other fundamental graph properties. We contrast the new algorithm with traditional ones.

No background in graph algorithms will be assumed.
Refreshments will be served in ECOT 831 immediately following the talk.
Hosted by Clarence (Skip) Ellis.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)