A Group Testing Problem on Two Disjoint Sets
Authors:
- Gerard J. ChangGCGerard J. Chang
- F. K. HwangFHF. K. Hwang
- 1 March 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 2 (1) , 35-38
Abstract
Recently the following group testing problem has been studied. We have two disjoint sets of items with cardinalities m and n respectively, where each set is known to contain exactly one defective item. The problem is to find the two defective items with a worst-case minimum number of group tests. It was conjectured that $\lceil \log _2 mn \rceil $ tests ($\lceil x \rceil $ denotes the smallest integer not less than x) always suffice. In this paper we prove that the conjecture is true.
Keywords
This publication has 1 reference indexed in Scilit:
- A Group Testing ProblemSIAM Journal on Algebraic Discrete Methods, 1980