A Variation of Cover-Free Families and Its Applications

A cover-free family is a family of subsets of a finite set in which no one is covered by the union of r others. We study a variation of cover-free family: A binary matrix is (r, w]-consecutive-disjunct if for any w cyclically consecutive columns [Formula: see text] and another r cyclically consecutive columns [Formula: see text], there exists one row intersecting [Formula: see text] but none of [Formula: see text]. In group testing, the goal is to determine a small subset of positive items D in a large population [Formula: see text] by group tests. By applying consecutive-disjunct matrices, we solve threshold group testing of consecutive positives in [Formula: see text] group tests nonadaptively, and the decoding complexity is [Formula: see text] where u is a threshold parameter in threshold group testing and it is assumed that |D|≤d and [Formula: see text]. Meanwhile, we obtain that for group testing of consecutive positives, all positives can be identified in [Formula: see text] group tests nonadaptively and the decoding complexity is [Formula: see text].