Zusammenfassung
Viele kombinatorische Probleme aus der Praxis sind NP-schwer; zu ihrer Lösung werden meist Heuristiken verwendet. Parametrisierte Komplexität ist ein neuerer Ansatz, der versucht, Strukturen von Praxisinstanzen auszunutzen. Ziel der Arbeit war es zu belegen, dass parametrisierte Komplexität, und insbesondere neuartige algorithmische Techniken, deren Entwicklung auf dieses Konzept zurückgeht, tatsächlich zu einsetzbaren Programmen für die exakte Lösung von Praxisinstanzen führt. Wir zeigen dies hier am Beispiel der Graphprobleme Clique Cover und Minimum-Weight Path, die Anwendungen in der Bioinformatik und anderen Gebieten haben.
Abstract
Many real-world problems are NP-hard; to solve them, usually heuristics are used. Parameterized Complexity is a recent approach that tries to exploit structures of real-world problem instances. The aim of the work was to establish that Parameterized Complexity, and in particular novel algorithmic techniques whose development was driven by this concept, can actually lead to practically useful programs for exactly solving real-world problem instances. We show this here using the example of Clique Cover und Minimum-Weight Path, which have applications in computational biology and other areas.
© by Oldenbourg Wissenschaftsverlag, München, Germany