title: Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems.
abstract: Fixed-parameter algorithms are designed to efficiently find optimal solutions to some computationally hard (NP-hard) problems by identifying and exploiting "small" problem-specific parameters. We survey practical techniques to develop such algorithms. Each technique is introduced and supported by case studies of applications to biological problems, with additional pointers to experimental results.
authors.affiliation: Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany.
authors.forename: Falk
authors.initials: F
authors.lastname: Hüffner
authors.affiliation: Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany. christian.komusiewicz@tu-berlin.de.
authors.forename: Christian
authors.initials: C
authors.lastname: Komusiewicz
authors.affiliation: Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany.
authors.forename: Rolf
authors.initials: R
authors.lastname: Niedermeier
authors.affiliation: Seven Bridges Genomics, Cambridge, MA, USA.
authors.forename: Sebastian
authors.initials: S
authors.lastname: Wernicke
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*
keywords: Algorithm design; Computational intractability; Discrete problems; Exponential running times; Fixed-parameter tractability; NP-hard problems; Optimal solutions