Improved strength four covering arrays with three symbols

DOI10.1007/S00373-017-1861-9MaRDI QIDQ1706436zbMATH OpenOpenAlexFDO

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)

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 756753 (Why is no real title available?)
• scientific article; zbMATH DE number 824935 (Why is no real title available?)
• Conditional expectation algorithms for covering arrays
• Covering arrays of strength three
• Group construction of covering arrays
• On the state of strength-three covering arrays
• Problems and algorithms for covering arrays
• Randomized post-optimization of covering arrays
• Software and hardware testing using combinatorial covering suites

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

Describes a project that uses

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)