Group testing: Revisiting the ideas
Articles
Viktor Skorniakov
Vilnius University
https://orcid.org/0000-0001-7260-6931
Remigijus Leipus
Vilnius University
Gediminas Juzeliūnas
Vilnius University
https://orcid.org/0000-0002-0677-6446
Kęstutis Staliūnas
Institució Catalana de Recerca i Estudis Avançats
https://orcid.org/0000-0002-0539-9538
Published 2021-05-01
https://doi.org/10.15388/namc.2021.26.23933
PDF

Keywords

group testing
quick sort algorithm
COVID-19

How to Cite

Skorniakov, V. (2021) “Group testing: Revisiting the ideas”, Nonlinear Analysis: Modelling and Control, 26(3), pp. 534–549. doi:10.15388/namc.2021.26.23933.

Abstract

The task of identification of randomly scattered “bad” items in a fixed set of objects is a frequent one, and there are many ways to deal with it. “Group testing” (GT) refers to the testing strategy aiming to effectively replace the inspection of single objects by the inspection of groups spanning more than one object. First announced by Dorfman in 1943, the methodology has underwent vigorous development, and though many related research still take place, the ground ideas remain the same. In the present paper, we revisit two classical GT algorithms: the Dorfman’s algorithm and the halving algorithm. Our fresh treatment of the latter and expository comparison of the two is devoted to dissemination of GT ideas, which are so important in the current COVID-19 induced pandemic situation.

PDF

Downloads

Download data is not yet available.