Algorithm design techniques for parameterized graph modification problems [Elektronische Ressource] / von Jiong Guo

Algorithm Design Techniques forParameterized Graph ModificationProblemsDissertationzur Erlangung des akademischen Gradesdoctor rerum naturalium (Dr.rer.nat.)vorgelegt dem Rat der Fakult¨at fu¨r Mathematik und Informatikder Friedrich-Schiller-Universit¨at Jenavon Dipl.-Inform. Jiong Guogeboren am 28.11.1970 in Chengdu, V. R. ChinaGutachter1. Prof. Rolf Niedermeier (Friedrich-Schiller-Universita¨t Jena)2. Prof. Michael R. Fellows (The University of Newcastle, Australien)3. Prof. Michael A. Langston (University of Tennessee, USA)Tag der letzten Pru¨fung des Rigorosums: 9. Feb. 2006Tag der o¨ffentlichen Verteidigung: 16. Feb. 2006Erk¨arungHiermiterkla¨reich,dassichdieArbeitselbst¨andigundnurmitdenangegebe-nen Hilfsmitteln angefertigt habe.Jena, April 2005 Jiong Guo5ZusammenfassungDieseArbeitbescha¨ftigtsichmitdemEntwurfparametrisierterAlgorithmenfu¨r Graphmodifikationsprobleme wie Feedback Vertex Set, Multicut inTrees,Cluster Editing,Closest 3-Leaf Power undMulticommodityDemand Flow in Trees.GraphensindheutzutageeinweitverbreitetesundoftverwendetesWerkzeugzur Modellierung komplexer Beziehungen zwischen einzelnen Objekten. Basie-rend auf solchen Graphmodellierungen k¨onnen viele in der Praxis auftretendeProbleme, die andernfalls nur sehr schwer zug¨anglich sind, in einer anschauli-chen und mathematisch pra¨zisen Form dargestellt werden.