Premium
New constructions for covering designs
Author(s) -
Gordon Daniel M.,
Patashnik Oren,
Kuperberg Greg
Publication year - 1995
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.3180030404
Subject(s) - combinatorics , mathematics , lexicographical order , set (abstract data type) , subnet , upper and lower bounds , discrete mathematics , computer science , mathematical analysis , programming language
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.