Abstract
A covering array t-CA(n, k, g), of size n, strength t, degree k, and order g, is a \(k\times n\) array on g symbols such that every \(t\times n\) sub-array contains every \(t\times 1\) 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, 3). The t-coverage of a testing array \(\mathscr {A}\) is the number of distinct t-tuples contained in the column vectors of \(\mathscr {A}\) divided by the total number of t-tuples. If the testing array is a covering array of strength t, its t-coverage is 100%. The covering arrays with budget constraints problem is the problem of constructing a testing array of size at most n having largest possible coverage, given values of t, k, g and n. This paper also presents several testing arrays with high 4-coverage.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akhtar, Y., Maity, S., Chandrasekharan, R.C.: Covering arrays of strength four and software testing. Springer Proc. Math. Stat. 139, 391–398 (2015)
Chateauneuf, M.A., Colbourn, C.J., Kreher, D.L.: Covering arrays of strength three. Designs Codes Cryptogr. 16, 235–242 (1999)
Chateauneuf, M.A., Kreher, D.L.: On the state of strength-three covering arrays. J. Combin. Design 10(4), 217–238 (2002)
Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The AETG system: an approach to testing based on combinatorial design. IEEE Trans. Softw. Eng. 23(7), 437–443 (1997)
Colbourn, C.J.: Covering array tables for \(t=2,3,4,5,6\). http://www.public.asu.edu/ccolbou/src/tabby/catable.html. Accessed 17 May 2017
Colbourn, C.J.: Conditional expectation algorithms for covering arrays. J. Combin. Math. Combin. Comput. 90, 97–115 (2014)
Covering Arrays generated by IPOG-F. http://math.nist.gov/coveringarrays/ipof/ipof-results.html. Accessed 1 May 2017
Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discrete Math. 284, 149–156 (2004)
Hartman, A.: Software and Hardware Testing Using Combinatorial Covering Suites. Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, vol. 34, pp. 237–266. Kluwer, Dordrecht (2006)
Kaner, C., Falk, J., Nguyen, H.Q.: Testing Computer Software, 2nd edn. Wiley, New York (1999)
Kuhn, D.R., Wallace, D.R., Gallo, A.M.: Software fault interactions and implications for software testing. IEEE Trans. Softw. Eng. 30(6), 418–421 (2004)
Maity, S.: 3-Way software testing with budget constraints. IEICE Trans. Inf. Syst. E–95–D(9), 2227–2231 (2012)
Maity, S., Nayak, A.: Improved test generation algorithms for pair-wise testing. In: Proceedings of 16th IEEE international symposium on software reliability engineering, Chicago, pp. 235–244 (2005)
Meagher, K., Stevens, B.: Group construction of covering arrays. J. Combin. Designs 13(1), 70–77 (2005)
Nayeri, P., Colbourn, C.J., Konjevod, G.: Randomized post-optimization of covering arrays. Eur. J. Combin. 34(1), 91–103 (2013)
Robinson, D.J.S.: A Course in the Theory of Groups, 2nd edn. Springer, New York (1995)
Yilmaz, C., Cohen, M., Porter, A.: Covering arrays for efficient fault characterisation in complex configuration spaces. IEEE Trans. Softw. Eng. 32(1), 20–34 (2006)
Acknowledgements
The second author gratefully acknowledges support from the Council of Scientific and Industrial Research (CSIR), India, during the work under CSIR senior research fellow scheme. The fourth author’s research was supported in part by the National Science Foundation under Grant No. 1421058.
Author information
Authors and Affiliations
Corresponding author
Additional information
An initial version of the paper has appeared in the proceedings of the Second International Conference on Mathematics sand Computing (ICMC 2015), India.
Rights and permissions
About this article
Cite this article
Maity, S., Akhtar, Y., Chandrasekharan, R.C. et al. Improved Strength Four Covering Arrays with Three Symbols. Graphs and Combinatorics 34, 223–239 (2018). https://doi.org/10.1007/s00373-017-1861-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1861-9