New constructions for covering designs

✍ Scribed by Daniel M. Gordon; Oren Patashnik; Greg Kuperberg

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 838 KB
• Volume: 3
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.3180030404

✦ Synopsis

A (v, k, t) covering design, or covering, is a family of k-subsets, called blocks, chosen from a wet, such that each t-subset 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 5 32, k 5 16, and t 5 8.