New constructions for covering designs

Daniel M. Gordon, Oren Patashnik, Greg Kuperberg

Journal of Combinatorial Designs · 1995 · 78 citations · 14 references

Concepts

TL;DR

A covering design A(v,k,t) is a family of k‑subsets of a v‑set such that every t‑subset lies in at least one block, and its minimum size is denoted C(v,k,t). The paper proposes three new construction methods for efficient coverings. These methods include a greedy algorithm akin to Conway and Sloane’s lexicographic code algorithm and two synthesis techniques that combine preexisting coverings. Using these techniques, the authors generate new upper‑bound tables for C(v,k,t) with v ≤ 32, k ≤ 16, and t ≤ 8. © 1995 John Wiley & Sons, Inc.

Abstract

Abstract A( v , k, t ) covering design , or covering , is a family of k ‐subnets, called blocks , chosen from a v ‐set, such that each t ‐subnet is contained in at least one of the blocks. The number of blocks is the covering's size , and the minimum size of such a covering is denoted by C(v,k,t) . This paper gives three new methods for constructing good coverings; a greedy algorithm similar to Conway and Sloane's algorithm for lexicographic codes [6], and two methods that synthesize new coverings from preexisting ones. Using these new methods, together with results in the literature, we build tables of upper bounds on C(v,k,t) for v ⩽ 32, k ⩽ 16, and t ⩽ 8. © 1995 John Wiley & Sons, Inc.

References

14