New constructions for covering designs

DOI10.1002/JCD.3180030404MaRDI QIDQ4373370zbMATH OpenOpenAlexFDO

Authors Daniel M. Gordon, Oren Patashnik, Greg Kuperberg

Publication date 15 April 1998

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9502238, http://www.escholarship.org/uc/item/3c66x4d1

zbMATH Keywords

greedy algorithmcovering design

Mathematics Subject Classification ID

Other designs, configurations (05B30) Combinatorial aspects of packing and covering (05B40)

Abstract: A $(v,k,t)$ {em covering design}, or {em covering}, is a family of $k$-subsets, called blocks, chosen from a $v$-set, such that each $t$-subset is contained in at least one of the blocks. The number of blocks is the covering's {em 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~cite{lex}, 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 $vleq32$, $kleq16$, and $tleq8$.%

Recommendations

• New coverings oft-sets with (t + 1)-sets
• General upper bounds on the minimum size of covering designs
• New upper bounds on the minimum size of covering designs
• Covering \(t\)-sets with \((t+2)\)-sets
• Asymptotically optimal covering designs

Cites work

• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 45817 (Why is no real title available?)
• On a packing and covering problem
• On coverings

Cited in

(30)

• scientific article; zbMATH DE number 4132175 (Why is no real title available?)
• On asymmetric coverings and covering numbers
• Connected coverings and an application to oriented matroids
• Some \(t\)-designs are minimal \((t+1)\)-coverings
• Small covering designs by branch-and-cut
• Asymptotic bounds for general covering designs
• Error-correcting codes from permutation groups
• Comparative analysis of topological constructions of sparse flat neighborhood networks for cluster supercomputers
• Optimal covering designs: complexity results and new bounds
• On some covering designs
• New construction of minimal (v,3,2)-coverings
• New coverings oft-sets with (t + 1)-sets
• Generalized covering designs and clique coverings
• The minimum likely column cover problem
• scientific article; zbMATH DE number 1792665 (Why is no real title available?)
• Connected Covering Numbers
• Constraint Orbital Branching
• New lower bounds for \(t\)-coverings
• New constructions of Lotto designs
• What we know and what we do not know about Turán numbers
• Uncoverings-by-bases for base-transitive permutation groups.
• An effective greedy heuristic for the social golfer problem
• Optimal partial clique edge covering guided by potential energy minimization
• Variable neighborhood descent heuristic for covering design problem
• General upper bounds on the minimum size of covering designs
• Renaming and the weakest family of failure detectors
• Towards a theory of intrusion detection
• Asymptotically optimal covering designs
• A tabu search algorithm for the covering design problem
• Upper bounds on the general covering numberC_λ(v,k,t,m)

This page was built for publication: New constructions for covering designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373370)