Treffer: Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems.
Title:
Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems.
Authors:
Hüffner F; Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany., Komusiewicz C; Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany. christian.komusiewicz@tu-berlin.de., Niedermeier R; Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany., Wernicke S; Seven Bridges Genomics, Cambridge, MA, USA.
Source:
Methods in molecular biology (Clifton, N.J.) [Methods Mol Biol] 2017; Vol. 1526, pp. 363-402.
Publication Type:
Journal Article; Research Support, Non-U.S. Gov't
Language:
English
Journal Info:
Publisher: Humana Press Country of Publication: United States NLM ID: 9214969 Publication Model: Print Cited Medium: Internet ISSN: 1940-6029 (Electronic) Linking ISSN: 10643745 NLM ISO Abbreviation: Methods Mol Biol Subsets: MEDLINE
Imprint Name(s):
Publication: Totowa, NJ : Humana Press
Original Publication: Clifton, N.J. : Humana Press,
Original Publication: Clifton, N.J. : Humana Press,
MeSH Terms:
Contributed Indexing:
Keywords: Algorithm design; Computational intractability; Discrete problems; Exponential running times; Fixed-parameter tractability; NP-hard problems; Optimal solutions
Entry Date(s):
Date Created: 20161130 Date Completed: 20180122 Latest Revision: 20180420
Update Code:
20250114
DOI:
10.1007/978-1-4939-6613-4_20
PMID:
27896752
Database:
MEDLINE
Weitere Informationen
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.