New constructions for covering designs

DOI10.1002/JCD.3180030404zbMATH Open0885.05053arXivmath/9502238OpenAlexW2008697975MaRDI QIDQ4373370FDOQ4373370

Oren Patashnik, Greg Kuperberg, Daniel M. Gordon

Publication date: 15 April 1998

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

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$.%

Full work available at URL: https://arxiv.org/abs/math/9502238

zbMATH Keywords

greedy algorithmcovering design

Mathematics Subject Classification ID

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

Cites Work

• On a packing and covering problem
• On coverings
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (27)

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

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)