New Algorithmic Paradigms in Exponential Time Algorithms

Difficult combinatorial problems typically require exponential time algorithms. Recently there is a new point of view that algorithms operating in (worst-case) exponential time can still be quite useful if the constants in the exponential complexity function are small enough. On the other hand, we do not know many algorithmic design principles for such algorithms up to now. This talk discusses various ways of designing good exponential time algorithms which reduce the value of the respective constants.

Authors and Affiliations

1. Abteilung Theoretische Informatik, Universität Ulm, 89069, Ulm, Germany

   Uwe Schöning

Editors and Affiliations

1. School of Mathematics, University of Leeds, LS2 9JT, Leeds, U.K.

   S. Barry Cooper

2. Department Mathematik, Universität Hamburg, Bundesstrasse 55, 20146, Hamburg, Germany

   Benedikt Löwe

3. Universiteit van Amsterdam,  

   Leen Torenvliet

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics