On the structure of small strength-2 covering arrays

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.

Keywords

bounds, computational enumeration, covering array

DOI

10.1002/jcd.21671

Citation

Kokkala, J, Meagher, K, Naserasr, R, Nurmela, K J, Östergård, P R J & Stevens, B 2020, 'On the structure of small strength-2 covering arrays', Journal of Combinatorial Designs, vol. 28, no. 1, pp. 5-24. https://doi.org/10.1002/jcd.21671

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201909255459

Collections

[article-cris] Sähkötekniikan korkeakoulu / ELEC

Show all metadata

On the structure of small strength-2 covering arrays

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series

Abstract

Description

Keywords

Other note

DOI

Citation

Permanent link to this item

Collections