Combinatorial group testing and its applications

목차 (Table of Contents)

• CONTENTS
• Preface = ⅴ
• Chapter 1 Introduction = 1
• 1.1 The History of Group Testing = 1
• 1.2 The Binary Tree Representation of a Group Testing Algorithm and Information Lower Bound = 5
• 1.3 The Structure of Group Testing = 7
• 1.4 Number of Group Testing Algorithms = 10
• 1.5 A Prototype Problem and Some Basic Inequalities = 12
• 1.6 Variations of the Prototype Problem = 17
• References = 18
• Chapter 2 General Algorithms = 19
• 2.1 Li's s-Stage Algorithm = 19
• 2.2 Hwang's Generalized Binary Splitting Algorithm = 20
• 2.3 The Nested Class = 23
• 2.4 (d,n) Algorithms and Merging Algorithms = 27
• 2.5 Some Practical Considerations = 30
• 2.6 An Application to Clone Screenings = 34
• References = 36
• Chapter 3 Algorithms for Special Cases = 38
• 3.1 Two Disjoint Sets Each Containing Exactly One Defective = 38
• 3.2 An Application to Locating Electrical Shorts = 43
• 3.3 The 2-Defective Case = 48
• 3.4 The 3-Defective Case = 53
• 3.5 When is Individual Testing Minimax? = 56
• 3.6 Identifying a Single Defective with Parallel Tests = 59
• References = 60
• Chapter 4 Nonadaptive Algorithms and Binary Superimposed Codes = 62
• 4.1 The Matrix Representation = 62
• 4.2 Basic Relations and Bounds = 63
• 4.3 Constant Weight Matrices and Random Codes = 68
• 4.4 General Constructions = 73
• 4.5 Special Constructions = 78
• References = 87
• Chapter 5 Multiaccess Channels and Extensions = 91
• 5.1 Multiaccess Channels = 92
• 5.2 Nonadaptive Algorithms = 96
• 5.3 Two Variations = 99
• 5.4 The k-Channel = 101
• 5.5 Quantitative Channel = 105
• References = 105
• Chapter 6 Some Other Group Testing Modules = 107
• 6.1 Symmetric Group Testing = 107
• 6.2 Some Additive Models = 109
• 6.3 A Maximum Model = 115
• 6.4 Some Models for d ＝ 2 = 118
• References = 123
• Chapter 7 Competitive Group Testing = 126
• 7.1 The First Competitiveness = 126
• 7.2 Bisecting = 128
• 7.3 Doubling = 132
• 7.4 Jumping = 134
• 7.5 The Second Competitiveness = 138
• 7.6 Digging = 140
• 7.7 Tight Bound = 143
• References = 148
• Chapter 8 Unreliable Tests = 149
• 8.1 Ulam's Problem = 149
• 8.2 General Lower and Upper Bounds = 155
• 8.3 Linearly Bounded Lies(1) = 160
• 8.4 The Chip Game = 164
• 8.5 Linearly Bounded Lies(2) = 168
• 8.6 Other Restrictions on Lies = 172
• References = 175
• Chapter 9 Optimal Search in One Variable = 177
• 9.1 Midpoint Strategy = 177
• 9.2 Fibonacci Search = 179
• 9.3 Minimum Root Identification = 183
• References = 190
• Chapter 10 Unbounded Search = 193
• 10.1 Introduction = 193
• 10.2 Bentley-Yao Algorithms = 195
• 10.3 Search with Lies = 199
• 10.4 Unbounded Fibonacci Search = 200
• References = 202
• Chapter 11 Group Testing on Graphs = 203
• 11.1 On Bipartite Graphs = 203
• 11.2 On Graphs = 205
• 11.3 On Hypergraphs = 207
• 11.4 On Trees = 212
• 11.5 Other Constraints = 216
• References = 217
• Chapter 12 Membership Problems = 218
• 12.1 Examples = 218
• 12.2 Polyhedral Membership = 220
• 12.3 Boolean Formulas and Decision Trees = 222
• 12.4 Recognition of Graph Properties = 226
• References = 229
• Chapter 13 Complexity Issues = 231
• 13.1 General Notions = 231
• 13.2 The Prototype Problem is in PSPACE = 233
• 13.3 Consistency = 234
• 13.4 Determinacy = 236
• 13.5 On Sample Space S(n) = 237
• 13.6 Learning by Examples = 243
• References = 244
• Index = 245