article

Problems and algorithms for covering arrays

Authors:

Leonid RaskinAuthors Info & Claims

Discrete Mathematics, Volume 284, Issue 1-3

Pages 149 - 156

https://doi.org/10.1016/j.disc.2003.11.029

Published: 01 July 2004 Publication History

Abstract

Covering arrays are combinatorial structures which extend the notion of orthogonal arrays and have applications in the realm of software testing. In this paper we raise several new problems motivated by these applications and discuss algorithms for their solution.

References

[1]

S.Y. Boroday, Determining essential arguments of Boolean functions, in: Proceedings of the Conference on Industrial Mathematics, Taganrog, 1998, pp. 59-61 (in Russian). (The translation is a personal communication from the author).

[2]

Bush, K.A, A generalization of the theorem due to MacNeish. Ann. Math. Statist. v23. 293-295.

[3]

Bush, K.A, Orthogonal arrays of index unity. Ann. Math. Statist. v23. 426-434.

[4]

Chateauneuf, M.A, Colbourn, C.J and Kreher, D.L, Covering arrays of strength 3. Des. Codes Cryptogr. v16. 235-242.

[5]

Chateauneuf, M.A and Kreher, D.L, On the state of strength 3 covering arrays. J. Combin. Des. v10. 217-238.

[6]

Cohen, D.M, Dalal, S.R, Fredman, M.L and Patton, G.C, The AETG system: an approach to testing based on combinatorial design. . IEEE Trans. Software Eng. v23. 437-444.

Digital Library

[7]

Colbourn, C.J and Dinitz, J.H, . 1996. CRC Press, Boca Raton, FL.

[8]

A. Hartman, Software and hardware testing using combinatorial covering suites, in: M.C. Golumbic and I.B.-A. Hartman (Eds.), Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms, to appear.

[9]

A. Hartman, L. Raskin, Combinatorial Test Services-a software package. Available at http://www.alphaworks.ibm.com/.

[10]

Y. Lei, K.C. Tai, In-parameter order: a test generation strategy for pairwise testing, in: Proceedings of the Third IEEE High Assurance Systems Engineering Symposium, Washington, DC, 1998, pp. 254-261.

[11]

L. Moura, J. Stardom, B. Stevens, A. Williams, Covering arrays with heterogeneous alphabet sizes, preprint June 2002.

[12]

Rényi, A, . 1971. Wiley, New York.

[13]

G. Roux, k-propriétés dans les tableaux de n colonnes; cas particulier de la k-surjectivité et de la k-permutativité, Ph.D. Dissertation, University of Paris 6, 1987.

[14]

Stevens, B, Ling, A and Mendelsohn, E, A direct construction of transversal covers using group divisible designs. Ars Combin. v63. 145-159.

[15]

Stevens, B and Mendelsohn, E, New recursive methods for transversal covers. J. Combin. Des. v7. 185-203.

[16]

Tang, D.T and Chen, C.L, Iterative exhaustive pattern generation for logic testing. IBM J. Res. Develop. v28. 212-219.

[17]

West, D.B, . 1996. Prentice-Hall, Englewood Cliffs, NJ.

[18]

A.W. Williams, Determination of test configurations for pair-wise interaction coverage, in: Proceedings of the 13th International Conference on the Testing of Communicating Systems (TestCom 2000), Ottawa Canada, 2000, pp. 59-74.

Cited By

Pira ERafe VEsfandyari S(2024)A three-phase approach to improve the functionality of t-way strategySoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08199-528:1(415-435)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00500-023-08199-5
Akhtar YMaity S(2024)Covering Array on the Cartesian Product of HypergraphsGraphs and Combinatorics10.1007/s00373-024-02813-540:4Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1007/s00373-024-02813-5
Guo XSong XZhou JWang FTang KWang Z(2023)A memetic algorithm for high‐strength covering array generationIET Software10.1049/sfw2.1213817:4(538-553)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1049/sfw2.12138
Show More Cited By

Problems and algorithms for covering arrays
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Theory of computation

Recommendations

Finite field constructions of combinatorial arrays

We survey a number of topics and constructions of combinatorial arrays based on finite fields. These combinatorial objects include orthogonal arrays, covering arrays, ordered orthogonal arrays, permutation arrays, frequency permutation arrays, ...
Covering arrays from cyclotomy

For a prime power $${q \equiv 1 (mod{v})}$$ , the q q cyclotomic matrix, whose entries are the discrete logarithms modulo v of the entries in the addition table of $${\mathbb{F}_q}$$ , has been shown using character theoretic arguments to produce an $${\varepsilon}$$ -biased array, provided that q is ...
Strength two covering arrays: Existence tables and projection

A covering arrayCA(N;t,k,v) is an Nxk array such that every Nxt sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used in experiments to screen for interactions among t-subsets of k ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Mathematics

Discrete Mathematics Volume 284, Issue 1-3

July, 2004

239 pages

ISSN:0012-365X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2004.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pira ERafe VEsfandyari S(2024)A three-phase approach to improve the functionality of t-way strategySoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08199-528:1(415-435)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00500-023-08199-5
Akhtar YMaity S(2024)Covering Array on the Cartesian Product of HypergraphsGraphs and Combinatorics10.1007/s00373-024-02813-540:4Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1007/s00373-024-02813-5
Guo XSong XZhou JWang FTang KWang Z(2023)A memetic algorithm for high‐strength covering array generationIET Software10.1049/sfw2.1213817:4(538-553)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1049/sfw2.12138
Chen JChen JCai SChen HZhang C(2023)A novel combinatorial testing approach with fuzzing strategyJournal of Software: Evolution and Process10.1002/smr.253735:12Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1002/smr.2537
Nasser AAbdul-Qawy AAbdullah NHujainah FZamli KGhanem W(2020)Latin Hypercube Sampling Jaya Algorithm based Strategy for T-way Test Suite GenerationProceedings of the 2020 9th International Conference on Software and Computer Applications10.1145/3384544.3384608(105-109)Online publication date: 18-Feb-2020
https://dl.acm.org/doi/10.1145/3384544.3384608
Ahmed BPahim AJunior CKuhn DBures MAli SGarousi V(2019)Towards an Automated Unified Framework to Run Applications for Combinatorial Interaction TestingProceedings of the 23rd International Conference on Evaluation and Assessment in Software Engineering10.1145/3319008.3319348(252-258)Online publication date: 15-Apr-2019
https://dl.acm.org/doi/10.1145/3319008.3319348
Leach KDougherty RSpensky CForrest SWeimer WPetke JTan SLangdon WWeimer W(2019)Evolutionary computation for improving malware analysisProceedings of the 6th International Workshop on Genetic Improvement10.1109/GI.2019.00013(18-19)Online publication date: 28-May-2019
https://dl.acm.org/doi/10.1109/GI.2019.00013
Maity SAkhtar YChandrasekharan RColbourn C(2018)Improved Strength Four Covering Arrays with Three SymbolsGraphs and Combinatorics10.1007/s00373-017-1861-934:1(223-239)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s00373-017-1861-9
Sarkar KColbourn CBonis AVaccaro U(2018)Partial Covering ArraysTheory of Computing Systems10.1007/s00224-017-9782-962:6(1470-1489)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s00224-017-9782-9
Galinier PKpodjedo SAntoniol GBosman P(2017)A penalty-based Tabu search for constrained covering arraysProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071324(1288-1294)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071324
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents