Combinatorial Group Testing and Its Applications

by Du, Ding-Zhu; Hwang, Frank K.

• ISBN13: 9789810212933
• ISBN10: 9810212933
• Format: Hardcover
• Copyright: 1993-10-01
• Publisher: World Scientific Pub Co Inc

Table of Contents

Preface	p. v
Preface to the Second Edition	p. vii
Introduction	p. 1
The History of Group Testing	p. 1
A Prototype Problem and Some General Remarks	p. 5
Some Practical Considerations	p. 7
References	p. 9
Sequential Group Testing Algorithms	p. 11
General Sequential Algorithms	p. 13
The Binary Tree Representation of a Sequential Algorithm	p. 13
The Structure of Group Testing	p. 20
Li's s-Stage Algorithm	p. 23
Hwang's Generalized Binary Splitting Algorithm	p. 24
The Nested Class	p. 27
(d, n) Algorithms and Merging Algorithms	p. 32
Number of Group Testing Algorithms	p. 35
References	p. 37
Sequential Algorithms for Special Cases	p. 39
Two Disjoint Sets Each Containing Exactly One Defective	p. 39
An Application to Locating Electrical Shorts	p. 44
The 2-Defective Case	p. 49
The 3-Defective Case	p. 54
When is Individual Testing Minimax?	p. 57
Identifying a Single Defective with Parallel Tests	p. 60
References	p. 62
Competitive Group Testing	p. 65
The First Competitiveness	p. 65
Bisecting	p. 67
Doubling	p. 71
Jumping	p. 73
The Second Competitiveness	p. 77
Digging	p. 80
Tight Bound	p. 82
References	p. 87
Unreliable Tests	p. 89
Ulam's Problem	p. 89
General Lower and Upper Bounds	p. 95
Linearly Bounded Lies (1)	p. 100
The Chip Game	p. 104
Linearly Bounded Lies (2)	p. 109
Other Restrictions on Lies	p. 112
References	p. 115
Complexity Issues	p. 117
General Notions	p. 117
The Prototype Group Testing Problem is in PSPACE	p. 119
Consistency	p. 120
Determinacy	p. 122
On Sample Space S(n)	p. 123
Learning by Examples	p. 129
References	p. 130
Nonadaptive Group Testing Algorithms	p. 131
Deterministic Designs and Superimposed Codes	p. 133
The Matrix Representation	p. 133
Basic Relations and Bounds	p. 134
Constant Weight Matrices	p. 140
General Constructions	p. 145
The Small d Cases	p. 151
References	p. 159
Random Designs and Error Tolerance	p. 163
Random Matrices	p. 163
Macula's Error Tolerance d-Disjunct Matrices	p. 167
q-Error-Tolerance d-Disjunct Matrices	p. 170
References	p. 175
DNA Applications	p. 177
Clone Library Screening	p. 177
Deterministic Designs	p. 180
Random Designs	p. 183
Some Additional Problems	p. 188
References	p. 192
Extended Group Testing Models	p. 195
Multiaccess Channels and Extensions	p. 197
Multiaccess Channels	p. 198
Nonadaptive Algorithms	p. 202
Two Variations	p. 205
The k-Channel	p. 208
Quantitative Channels	p. 211
References	p. 211
Additive Model and Others	p. 213
Symmetric Group Testing	p. 213
Some Additive Models	p. 215
A Maximum Model	p. 221
Some Models for d = 2	p. 224
References	p. 230
Group Testing on Graphs	p. 233
2-Optimal Graphs	p. 233
Solution of the Du-Hwang Conjecture	p. 236
Defective Vertices	p. 242
On Trees	p. 245
Other Constraints	p. 250
References	p. 250
Other Related Searching Problems	p. 253
Optimal Search in One Variable	p. 255
Midpoint Strategy	p. 255
Fibonacci Search	p. 257
Minimum Root Identification	p. 261
References	p. 268
Unbounded Search	p. 271
Introduction	p. 271
Bentley-Yao Algorithms	p. 273
Search with Lies	p. 277
Unbounded Fibonacci Search	p. 279
References	p. 280
Membership Problems	p. 281
Examples	p. 281
Polyhedral Membership	p. 283
Boolean Formulas and Decision Trees	p. 285
Recognition of Graph Properties	p. 289
References	p. 292
Counterfeit Coins	p. 295
One Counterfeit Coin	p. 295
Two, Three, and More Counterfeit Coins	p. 301
The All-Equal Problem	p. 302
Anti-Hadamard Matrices	p. 308
Coins with Arbitrary Weights	p. 314
References	p. 315
Index	p. 319
Table of Contents provided by Syndetics. All Rights Reserved.