A Group Testing Problem on Two Disjoint Sets

Authors:
  • GCGerard J. Chang
    Gerard J. Chang
  • FHF. K. Hwang
    F. K. Hwang

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.

This publication has 1 reference indexed in Scilit: