Monday, September 18, 2006
11:00 AM
CSB 209
Joerg Rothe
Improving Exponential-Time Algorithms for NP-Complete Problems
NP-complete problems cannot have deterministic polynomial-time algorithms unless P = NP. Due to their importance in practive, however, it is useful to improve their known exponential-time algorithms. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and domatic number.

Bio: Ph.D. in 1995 and Habilitation degree in 1999, both from Friedrich-Schiller-Universitaet Jena, Germany. Visiting Scholar (1993-1994) and Visiting Assistant Professor (1997-1998) at the University of Rochester. Heisenberg Fellowship from the Deutsche Forschungsgemeinschaft in 2000. Associate Professor for Theoretical Computer Science at Heinrich-Heine-Universitaet Duesseldorf, Germany, since 2000. Research areas: computational complexity theory, cryptology, and algorithmics.