Journal of Combinatorial Designs · 1995 · 78 citations · 14 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsSet TheoryCoding TheoryCombinatorial OptimizationGreedy AlgorithmsCovering DesignsCovering ProblemsGreedy ApproximationGreedy HeuristicsSet Cover ProblemSubnet DesignSubnetsUpper Bounds
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 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.
14
The Art of Computer Programming
G.E. Whitesides · Nuclear Science and Engineering · 1970 · 6.1K citations
A new table of constant weight codes
A.E. Brouwer, James B. Shearer, N. J. A. Sloane et al. · IEEE Transactions on Information Theory · 1990 · 434 citations
On a Packing and Covering Problem
Vojtěch Rödl · European Journal of Combinatorics · 1985 · 414 citations
Johanan Schonheim · Pacific Journal of Mathematics · 1964 · 172 citations · Full text