Improved upper bounds for several variants of group testing [Elektronische Ressource] / vorgelegt von Andreas Allemann

Improved Upper Bounds forSeveral Variants of Group TestingVon der Fakult¨at fur¨ Mathematik, Informatik und Naturwissenschaftender Rheinisch-Westf¨alischen Technischen Hochschule Aachenzur Erlangung des akademischen Grades eines Doktorsder Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-MathematikerAndreas Allemannaus BonnBerichter: Universit¨atsprofessor Dr. Eberhard TrieschProfessor Dr. Lutz VolkmannTag der mundlic¨ hen Prufung:¨ 11. November 2003Diese Dissertation ist auf den Internetseiten der Hochschulbibliothekonline verfug¨ bar.iiContentsIntroduction 11 On the Structure of Group Testing 51.1 The Group Testing Model . . . . . . . . . . . . . . . . . . . . 51.2 The Test Information Hypergraph . . . . . . . . . . . . . . . 61.3 Identifying an Unknown Number of Defectives . . . . . . . . 81.4 Identifying a Bounded Number of Defectives . . . . . . . . . . 102 Complete Group Testing 152.1 Variants of Combinatorial Group Testing . . . . . . . . . . . 152.2 Complete Related to (d,n) Group Testing . . . . . . . . . . . 163 The Split and Overlap Algorithm 193.1 Nested Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Overview of the Split and Overlap Algorithm . . . . . . . . . 213.3 Overlapping Subalgorithms . . . . . . . . . . . . . . . . . . . 223.4 Cost Estimate of Subalgorithms . . . . . . . . . . . . . . . . . 273.5 Scaling up Subalgorithms . . . . . . . . . . . . . . . . . . . . 293.6 Fixed Size Algorithms . .