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 t-tuple 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ős-Ko-Rado 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 strength-2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength-2 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 (from-to) | 5-24 |
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 article-refereed |
Keywords
- bounds
- computational enumeration
- covering array
Fingerprint
Dive into the research topics of 'On the structure of small strength-2 covering arrays'. Together they form a unique fingerprint.Datasets
-
Classification of small strength-2 covering arrays
Kokkala, J. (Creator), Meagher, K. (Creator), Reza, N. (Creator), Nurmela, K. (Creator), Östergård, P. (Creator) & Stevens, B. (Creator), Zenodo, 31 Oct 2018
Dataset
Projects
- 1 Finished
-
Construction and Classification of Discrete Mathematic Structures
Östergård, P. (Principal investigator)
01/09/2015 → 31/08/2019
Project: Academy of Finland: Other research funding