On combinatorial search problems which involve graphs [Elektronische Ressource] / vorgelgt von Torsten Korneffel

On Combinatorial Search Problems Which InvolveGraphsVon der Fakult¨at fu¨r Mathematik, Informatik und Naturwissenschaftender Rheinisch-Westf¨alischen Technischen Hochschule Aachenzur Erlangung des akademischen Gradeseines Doktors der Naturwissenschaftengenehmigte Dissertationvorgelegt vonDiplom-MathematikerTorsten Korneffelaus BaunatalBerichter: Universit¨atsprofessor Dr. Eberhard TrieschProfessor Dr. Yubao GuoTag der mu¨ndlichen Pru¨fung: 08.02.2007Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek onlineverfu¨gbar.iiDanksagungMein Dank gilt Herrn Prof. Dr. Eberhard Triesch fu¨r die Unterstu¨tzungbei der Suche nach interssanten Suchproblemen und nach Verbesserungen undVereinfachungen und fu¨r seine Betreuung im Graduiertenkolleg.Allen Mitarbeitern des Lehrstuhls danke ich fu¨r gute Zusammenarbeit, sehrangenehme Atmosf¨are und (mea culpa) immer sp¨atere aber zu der Atmosf¨arebeitragende Fru¨hstu¨cksrunden. Und einer langen Reihe von wissenschaftlichenMitarbeitern auch fu¨r vieles außerhalb der Arbeit, aber mit positiven Einflussauf die selbige und die sch¨one Zeit in Aachen.Außerdem danke ich meinen Eltern fu¨r ihre geduldige Unterstu¨tzung im allge-meinen und w¨ahrend der Promotion im besonderen.PrefaceReality provides many examples of something we call a search. Informally, wemayhaveagoal(e.g.,findingalostkey, adamagedlightbulb,theshortestwayto the next bus stop) and a set of possible actions to gain some information.