Covering \(t\)-sets with \((t+2)\)-sets
type: Item
instance of: scholarly article
title: Covering \(t\)-sets with \((t+2)\)-sets
zbMATH Open document ID: 0935.05030
DOI: 10.1016/S0166-218X(99)00090-6
author: Kari J. Nurmela
author: Patric R. J. Östergård
published in: Discrete Applied Mathematics
publication date: 2000-04-26T00:00:00Z
review text: Let \(X\) be a \(v\)-set of points and \({\mathcal B}\) be a family of \(k\)-subsets of \(X\), called blocks. Then the pair \((X,{\mathcal B})\) is called a \(t\)-\((v,k,\lambda)\) covering design if each \(t\)-subset of \(X\) is contained in (or is covered by) at least \(\lambda\) blocks. The minimum size of \({\mathcal B}\) is denoted by \(C_{\lambda}(v,k,t)\). The authors consider a computer method for the construction of covering designs when \(\lambda=1\), thus obtaining upper bounds on \(C_1(v,k,t)\). Their computer search firstly assumes some automorphisms of desired covering designs and then acts as a tabu search. The results for \(k=t+2\) are presented in a updated table of upper bounds for \(C_1(v,t+2,t)\) where \(v \leq 28\) and \(3 \leq t \leq 8\). Some new designs are explicitely given.
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 05B05
zbMATH DE Number: 1340651
zbMATH Keywords: automorphism group
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: covering design
zbMATH Keywords: tabu search
reviewed by: Peter Boyvalenkov
MaRDI profile type: Publication
full work available at URL: s0166-218x(99)00090-6
OpenAlex ID: W1972207399
description: scientific article; zbMATH DE number 1340651