Projects per year
Abstract
A covering array CA(N; t, k, v) of strength t is an N × k array of symbols from an alphabet of size v such that in every N × t subarray, every ttuple occurs in at least one row. A covering array is optimal if it has the smallest possible N for given t, k, and v, and uniform if every symbol occurs [N∕v] or [N∕v] times in every column. Before this paper, the only known optimal covering arrays for t = 2 were orthogonal arrays, covering arrays with v = 2 constructed from Sperner's Theorem and the ErdősKoRado Theorem, and 11 other parameter sets with v > 2 and N > v2. In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper, a new lower bound as well as structural constraints for small uniform strength2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength2 covering array with v > 2 and N > v2 is now known for 21 parameter sets. Our constructive results continue to support the conjecture.
Original language  English 

Pages (fromto)  524 
Number of pages  20 
Journal  Journal of Combinatorial Designs 
Volume  28 
Issue number  1 
Early online date  1 Jan 2019 
DOIs  
Publication status  Published  Jan 2020 
MoE publication type  A1 Journal articlerefereed 
Keywords
 bounds
 computational enumeration
 covering array
Fingerprint
Dive into the research topics of 'On the structure of small strength2 covering arrays'. Together they form a unique fingerprint.Datasets

Classification of small strength2 covering arrays
Kokkala, J. (Creator), Meagher, K. (Creator), Reza, N. (Creator), Nurmela, K. (Creator), Östergård, P. (Creator) & Stevens, B. (Creator), 31 Oct 2018
Dataset
Projects
 1 Finished

Construction and Classification of Discrete Mathematic Structures
Kokkala, J., Laaksonen, A., Östergård, P., Szollosi, F. & Pöllänen, A.
01/09/2015 → 31/08/2019
Project: Academy of Finland: Other research funding