Premium
A density‐based greedy algorithm for higher strength covering arrays
Author(s) -
Bryce Renée C.,
Colbourn Charles J.
Publication year - 2009
Publication title -
software testing, verification and reliability
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.216
H-Index - 49
eISSN - 1099-1689
pISSN - 0960-0833
DOI - 10.1002/stvr.393
Subject(s) - complement (music) , pairwise comparison , logarithm , computer science , function (biology) , test (biology) , greedy algorithm , algorithm , software , upper and lower bounds , code coverage , theoretical computer science , mathematics , artificial intelligence , programming language , mathematical analysis , paleontology , biochemistry , chemistry , complementation , evolutionary biology , biology , gene , phenotype
Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t ‐way interactions with t ≥3. This study extends an efficient density‐based algorithm for pairwise coverage to generate t ‐way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one‐test‐at‐a‐time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd.