Random combinatorial structures and randomized search heuristics [Elektronische Ressource] / vorgelegt von Daniel Johannsen

Random Combinatorial Structuresand Randomized Search HeuristicsDissertationzur Erlangung des Grades desDoktors der Naturwissenschaftender Naturwissenschaftlich-Technischen Fakultätender Universität des Saarlandesvorgelegt vonDaniel JohannsenSaarbrücken7. April 20102Tag des Kolloquiums:15. Juli 2010Dekan der Naturwissenschaftlich-Technischen Fakultät I:Prof. Dr. Holger HermannsPrüfungsausschuss:Prof. Dr. Benjamin DoerrProf. Dr. Kurt MehlhornProf. Dr. Thomas Lengauer (Vorsitzender des Prüfungsausschusses)Dr. Tobias Friedrich (Akademischer Beisitzer)Berichterstatter:Prof. Dr. Benjamin DoerrProf. Dr. Kurt MehlhornProf. Xin Yao3AbstractThis thesis is concerned with the probabilistic analysis of random combinatorial struc-tures and the runtime analysis of randomized search heuristics.On the subject of random structures, we investigate two classes of combinatorialobjects. The first is the class of planar maps and the second is the class of generalizedparking functions. We identify typical properties of these structures and show strongconcentration results on the probabilities that these properties hold. To this end, wedevelop and apply techniques based on exact enumeration by generating functions. Forseveral types of random planar maps, this culminates in concentration results for thedegree sequence. For parking functions, we determine the distribution of the defect,the most characteristic parameter.