Abstract
In this paper we study a new, generalized version of the well-known group testing problem. In the classical model of group testing we are given n objects, some of which are considered to be defective. We can test certain subsets of the objects whether they contain at least one defective element. The goal is usually to find all defectives using as few tests as possible. In our model the presence of defective elements in a test set Q can be recognized if and only if their number is large enough compared to the size of Q. More precisely for a test Q the answer is yes if and only if there are at least α|Q| defective elements in Q for some fixed α.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahlswede, R., Deppe, C., Lebedev, V.: Finding one of D defective elements in some group testing models. Probl. Inf. Transm. 48(2), 173–181 (2012)
Damaschke, P.: The Algorithmic Complexity of Chemical Treshold Testing. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 205–216. Springer, Heidelberg (1997)
De Bonis, A., Gargano, L., Vaccaro, U.: Efficient algorithms for chemical threshold testing problems. Theoret. Comput. Sci. 259(1-2), 493–511 (2001)
Dorfman, R.: The Detection of defective members of large populations. Ann. Math. Statistics 14, 436–440 (1943)
Du, D.Z., Hwang, F.K.: Combinatorial Group Testing and Its Applications, 1st edn. World Scientific (1994)
Katona, G.O.H.: On separating systems of a finite set. J. Combinatorial Theory 1, 174–194 (1966)
Katona, G.O.H.: Rènyi and the Combinatorial Search Problems. Studia Sci. Math. Hungar. 26, 363–378 (1991)
Wegener, I.: On separating systems whose elements are sets of at most k elements. Discrete Math 28, 219–222 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Gerbner, D., Keszegh, B., Pálvölgyi, D., Wiener, G. (2013). Density-Based Group Testing. In: Aydinian, H., Cicalese, F., Deppe, C. (eds) Information Theory, Combinatorics, and Search Theory. Lecture Notes in Computer Science, vol 7777. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36899-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-36899-8_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36898-1
Online ISBN: 978-3-642-36899-8
eBook Packages: Computer ScienceComputer Science (R0)