On the structure of small strength-2 covering arrays

Janne Kokkala, Karen Meagher, Reza Naserasr, Kari J. Nurmela, Patric R.J. Östergård, Brett Stevens*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 languageEnglish
Pages (from-to)5-24
JournalJournal of Combinatorial Designs
Volume28
Issue number1
Early online date1 Jan 2019
DOIs
Publication statusPublished - Jan 2020
MoE publication typeA1 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.

  • Projects

    Construction and Classification of Discrete Mathematic Structures

    Kokkala, J., Laaksonen, A., Heinlein, D., Ganzhinov, M., Östergård, P. & Szollosi, F.

    01/09/201524/09/2019

    Project: Academy of Finland: Other research funding

    Cite this

    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, 28(1), 5-24. https://doi.org/10.1002/jcd.21671