Improved strength four covering arrays with three symbols

DOI10.1007/S00373-017-1861-9zbMATH Open1386.05017arXiv1509.03547OpenAlexW2963486547MaRDI QIDQ1706436FDOQ1706436

Authors: Soumen Maity, Yasmeen Akhtar, Reshma C. Chandrasekharan, Charles J. Colbourn 

Publication date: 22 March 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A covering array $t$-$CA(n,k,g)$, of size $n$, strength $t$, degree $k$, and order $g$, is a $kimesn$ array on $g$ symbols such that every $timesn$ sub-array contains every $times1$ column on $g$ symbols at least once. Covering arrays have been studied for their applications to software testing, hardware testing, drug screening, and in areas where interactions of multiple parameters are to be tested. In this paper, we present an algebraic construction that improves many of the best known upper bounds on $n$ for covering arrays 4-$CA(n,k,g)$ with $g=3$. The $coverage$ $measure$ $m{u}_t(A)$ of a testing array $A$ is defined by the ratio between the number of distinct $t$-tuples contained in the column vectors of $A$ and the total number of $t$-tuples. A covering array is a testing array with full coverage. The $covering$ $arrays$ $with$ $budget$ $constraints$ $problem$ is the problem of constructing a testing array of size at most $n$ having largest possible coverage measure, given values of $k,g$ and $n$. This paper presents several strength four testing arrays with high coverage. The construction here is a generalisation of the construction methods used by Chateauneuf, Colbourn and Kreher, and Meagher and Stevens.

Full work available at URL: https://arxiv.org/abs/1509.03547

Recommendations

• Constructions of covering arrays of strength five
• On the state of strength-three covering arrays

zbMATH Keywords

automorphism groupcoveragecovering arrayprojective general linear group

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Other designs, configurations (05B30) Combinatorial aspects of packing and covering (05B40)

Cites Work

• Problems and algorithms for covering arrays
• Title not available (Why is that?)
• On the state of strength-three covering arrays
• Software and hardware testing using combinatorial covering suites
• Covering arrays of strength three
• Group construction of covering arrays
• Title not available (Why is that?)
• Conditional expectation algorithms for covering arrays
• Randomized post-optimization of covering arrays

Cited In (8)

• Asymptotic and constructive methods for covering perfect hash families and covering arrays
• Roux-type constructions for covering arrays of strengths three and four
• Tower of covering arrays
• On the state of strength-three covering arrays
• Covering arrays of strength 3 and 4 from holey difference matrices
• Conditional expectation algorithms for covering arrays
• Arrays for combinatorial interaction testing: a review on constructive approaches
• Constructions of covering arrays of strength five

Uses Software

• AETG

This page was built for publication: Improved strength four covering arrays with three symbols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706436)