The domatic number problem: Boolean hierarchy completeness and exact exponential time algorithms [Elektronische Ressource] / vorgelegt von Tobias Riege

The Domatic Number Problem:Boolean Hierarchy Completeness andExact Exponential-Time AlgorithmsDissertationzur Erlangung des Doktorgrades derMathematisch-Naturwissenschaftlichen Fakult¨atder Heinrich-Heine-Universit¨at Du¨sseldorfvorgelegt vonTobias Riegegeboren in HalternDu¨sseldorf, im November 2006Aus dem Institut fu¨r Informatik derHeinrich-Heine-Universit¨at Du¨sseldorfGedruckt mit der Genehmigung derMathematisch-Naturwissenschaftlichen Fakult¨at derHeinrich-Heine-Universit¨at Du¨sseldorfReferent: Prof. Dr. J¨org RotheKoreferent: Prof. Dr. Egon WankeTag der mu¨ndlichen Pru¨fung: 20.12.2006iiiAcknowledgmentsI want to thank my thesis advisor J¨org Rothe for all of his support duringthe past four years. In the first place, I am deeply gratefulto him forgivingme the chance to be part of his research team. Without his great efforts,I would never have had the chance to work in the scientific community.Many inspiring and valuable discussions with him initiated fruitful ideasthat led to the research presented in this thesis. I am very thankful to himfor letting me have a share of his mathematical precision. In addition, hisprofound knowledge of the English language helped a great deal to spice upour articles.Next I would like to thank all my coauthors, including J¨org Rothe,G´abor Erd´elyi, Holger Spakowski, and Masaki Yamamoto.