Algorithms and experiments for parameterized approaches to hard graph problems [Elektronische Ressource] / von Falk Hüffner

Algorithms and Experiments forParameterized Approaches toHard Graph ProblemsDissertationzur Erlangung des akademischen Gradesdoctor rerum naturalium (Dr. rer. nat.)¨ ¨vorgelegt dem Rat der Fakultat fur Mathematik und Informatikder Friedrich-Schiller-Universitat¨ Jenavon Dipl.-Inform. Falk Huf¨ fnergeboren am 25. 02. 1976 in Oldenburg (Oldenburg)Gutachter1. Prof. Dr. Rolf Niedermeier (Friedrich-Schiller-Universitat¨ Jena)2. Prof. Dr. Michael R. Fellows (The University of Newcastle, Australien)3. Prof. Dr. Peter Rossmanith (Rheinisch-Westfalische¨ Technische HochschuleAachen)Tag der letzten Prufung¨ des Rigorosums: 17. Dezember 2007Tag der of¨ fentlichen Verteidigung: 19. Dezember 2007ZusammenfassungDiese Dissertation beschaftigt¨ sich mit Entwurf, Analyse, Implementierung und¨experimenteller Bewertung von Algorithmen fur schwere Graphprobleme. DasZiel ist es zu belegen, dass das Konzept der parametrisierten Komplexitat¨ , undinsbesondere neuartige algorithmische Techniken, deren Entwicklung auf diesesKonzept zuruckgeht,¨ zu einsetzbaren Programmen fur¨ die exakte Losung¨ vonPraxisinstanzen fuhrt.¨Insbesondere untersuchen wir die drei Graphprobleme Clique Cover, Ba-lanced Subgraph und Minimum-Weight Path. Beim Clique Cover-Problem istdie Aufgabe, eine kleinstmogliche¨ Menge von Cliquen zu finden, die alle Kantenabdeckt. Es hat Anwendungen in Compileroptimierung, geometrischen Berech-nungsproblemen und angewandter Statistik.