2016/07/02 by D'yachkov, A. G., Vorobyev, I. V., Polyanskii, N. A. +1
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1607.00511
Group testing is a well known search problem that consists in detecting up to s defective elements of the set [t]=\1,…,t\ by carrying out tests on properly chosen subsets of [t]. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defects. For the case s=2, we design an explicit construction, which makes use of 2log2t(1+o(1)) tests in the worst case and consists of 4 stages.