Recent time has seen quite some progress in the development of
exponential
time algorithms for NP-hard problems, where the base of the
exponential term is fairly small.
These developments are also tightly related to the theory of fixed
parameter
tractability.
In this incomplete survey, we explain some basic techniques in
the design of efficient fixed parameter algorithms,
discuss deficiencies of parameterized complexity theory, and try to
point out some future research challenges.
The focus of this paper is on
the design of efficient algorithms and not on a structural theory
of parameterized complexity.
Moreover, our emphasis will be laid on two
exemplifying issues: Vertex Cover and
MaxSat problems.
CV:
Date of birth: July 21, 1966 in Munich, Fed.
Rep. of Germany.
Citizenship: German.
1986--1991: Student of Computer Science (Mathematics) at the
Technische Universiaet Muenchen.
1991: Received diploma in computer science.
1991--1994: Research assistant in the theoretical computer
science group
at the Technische Universitaet Muenchen.
1994-- : Research assistant in the theoretical computer science
group
at the Unversitaet Tuebingen.
1996: Doctorate (PH.D.) from the Unversitaet Tuebingen, WSI fuer
Informatik.
1998: Feodor Lynen fellowship of the Alexander von
Humboldt-Stiftung,
Bonn, and the Center for Discrete Mathematics, Theoretical
Computer Science and Applications (DIMATIA), Praha.
http://www-fs.informatik.uni-tuebingen.de/~niedermr