Tracing a single user
From MaRDI portal
Denote \(g(n,r)\) the maximum possible cardinality of a family of subsets of an \(n\)-element underlying set so that given a union of at most \(r\) members, one can identify at least one of the members. This has a close connection with the so-called group testing problem applied to design DNA chips in molecular biology. The paper shows that \(g(n,r)=2^{\Theta({n \over r})}.\) The main contribution of the paper is a new lower bound for \(g(n,r)\).
Recommendations
- Tracing Many Users With Almost No Rate Penalty
- scientific article; zbMATH DE number 910893
- Strict group testing and the set basis problem
- On the structure of a class of sets useful in nonadaptive group testing
- Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
Cites work
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Algorithmic construction of sets for k -restrictions
- Bounds on the length of disjunctive codes
- Families of finite sets in which no set is covered by the union of \(r\) others
- scientific article; zbMATH DE number 4043100 (Why is no real title available?)
- scientific article; zbMATH DE number 956611 (Why is no real title available?)
- Learning a Hidden Matching
- New bounds for union-free families of sets
- Nonrandom binary superimposed codes
- On r-cover-free families
- On the upper bound of the size of the \(r\)-cover-free families
- Single-User Tracing and Disjointly Superimposed Codes
Cited in
(3)
This page was built for publication: Tracing a single user
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850073)
