Algorithmics and Computational Complexity

Parameterized Algorithmics for Bioinformatics (PABI)

Synopsis

The project "Parameterized algorithmics for bioinformatics (PABI)" heads at exploring and understanding the reasons for computational intractability (NP-hardness) of a large number of problems in algorithmic bioinformatics. As it turned out in recent years, the hardness of these problems can often be attributed to problem-specific parameters. In particular, if these problem parameters are small - and if the seemingly unavoidable combinatorial explosion inherent to the NP-hard problems can be confined to these parameters - then the concept of fixed-parameter tractability may offer an opportunity for efficient (and exact) algorithms despite NP-hardness.

Funded by

Deutsche Forschungsgemeinschaft (Project PABI, NI 369/7)

Time

October 2007 - February 2014

Head: Rolf Niedermeier

People

Falk Hüffner

Former member