Density-based group testing

DOI10.1007/978-3-642-36899-8_27MaRDI QIDQ4915256zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Gábor Wiener

Publication date 9 April 2013

Published in Information Theory, Combinatorics, and Search Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1464

zbMATH Keywords

group testingquerysearch

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Theory of error-correcting codes and error-detecting codes (94B99)

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 alpha |Q| defective elements in Q for some fixed alpha.

Recommendations

• Bounds for nonadaptive group tests to estimate the amount of defectives
• Group testing problem with two defectives
• An efficient algorithm for combinatorial group testing
• Finding one of D defective elements in some group testing models
• Bounds for nonadaptive group tests to estimate the amount of defectives

Cites work

• Efficient algorithms for chemical threshold testing problems
• Finding one of D defective elements in some group testing models
• scientific article; zbMATH DE number 168147 (Why is no real title available?)
• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• On separating systems of a finite set
• On separating systems whose elements are sets of at most k elements

Cited in

(10)

• Smart elements in combinatorial group testing problems
• Quaternary splitting algorithm in group testing
• Error-tolerant nonadaptive interval group testing with density-based tests
• On a parity based group testing algorithm
• scientific article; zbMATH DE number 4016572 (Why is no real title available?)
• Finding a majority ball with majority answers
• Finding one of D defective elements in some group testing models
• Threshold and Majority Group Testing
• Group Testing With Nested Pools
• Finding a non-minority ball with majority answers

This page was built for publication: Density-based group testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4915256)