Mixed-level detecting arrays on graphs

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

The purpose of this paper was to develop a unified combinatorial framework for fault localization in heterogeneous software systems, where parameters may have different numbers of levels. Specifically, we investigated mixed-level detecting arrays (MDAs) on graphs, extending the classical detecting array model to accommodate non-uniform factor structures. In this paper, we established an optimality criterion that minimizes the number of required test cases and analyzes the structural and combinatorial properties of optimal MDAs on graphs. Furthermore, several constructive methods were proposed to generate optimal arrays, and existence results were derived that achieve the theoretical lower bounds. The findings enhance the theoretical understanding of detecting arrays in graph-based settings and provide practical guidelines for designing cost-efficient and fault-sensitive test suites in complex, heterogeneous software systems.

Keywords

combinatorial testing / detecting arrays / mixed-level factors / graph-based testing / optimality criterion

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] D. R. Kuhn, R. N. Kacker, Y. Lei, Introduction to Combinatorial Testing, Chapman and Hall/CRC, Boca Raton, FL, USA, 2013.

[2] C. Nie, H. Leung, A survey of combinatorial testing, ACM Comput. Surv., 43 (2011), 1-29. https://doi.org/10.1145/1883612.1883618

[3] C. J. Colbourn, Strength two covering arrays: Existence tables and projection, Discrete Math., 308 (2008), 772-786. https://doi.org/10.1016/j.disc.2007.07.050

[4] J. T. Jimenez, I. I. Marquez, Covering arrays of strength three from extended permutation vectors, Des. Codes Cryptogr., 86 (2018), 2629-2643. https://doi.org/10.1007/s10623-018-0465-6

[5] J. T. Jimenez, I. I. Marquez, Improved covering arrays using covering perfect hash families with groups of restricted entries, Appl. Math. Comput., 369 (2020), 124826. https://doi.org/10.1016/j.amc.2019.124825

[6] L. Ji, J. Yin, Constructions of new orthogonal arrays and covering arrays of strength three, J. Comb. Theory Ser. A, 117 (2010), 236-247. https://doi.org/10.1016/j.jcta.2009.06.002

[7] L. G. Hernandez, New bounds for mixed covering arrays in t-way testing with uniform strength, Inf. Softw. Technol., 59 (2024), 17-32. https://doi.org/10.1016/j.infsof.2014.10.009

[8] I. I. Marquez, J. T. Jimenez, B. A. Juárez, H. A. George, A greedy-metaheuristic 3-stage approach to construct covering arrays, Inf. Sci., 460-461 (2018), 172-189. https://doi.org/10.1016/j.ins.2018.05.047

[9] K. Sarkar, C. J. Colbourn, Two-stage algorithms for covering array construction, J. Comb. Des., 27 (2019), 475-505. https://doi.org/10.1002/jcd.21657

[10] K. Shokri, L. Moura, New families of strength 3 covering arrays using linear feedback shift register sequences, J. Comb. Des., 33 (2025), 156-171. https://doi.org/10.1002/jcd.21963

[11] S. Raaphorst, L. Moura, B. Stevens, A construction for strength-3 covering arrays from linear feedback shift register sequences, Des. Codes Cryptogr., 73 (2014), 949-968. https://doi.org/10.1007/s10623-013-9835-2

[12] G. Tzanakis, L. Moura, D. Panario, B. Stevens, Covering arrays from m-sequences and character sums, Des. Codes Cryptogr., 85 (2017), 437-456. https://doi.org/10.1007/s10623-016-0316-2

[13] C. J. Colbourn, C. Shi, C. M. Wang, J. Yan, Mixed covering arrays of strength three with few factors, J. Stat. Plann. Inference, 141 (2011), 3640-3647. https://doi.org/10.1016/j.jspi.2011.05.018

[14] L. Moura, J. Stardom, B. Stevens, A. Williams, Covering arrays with mixed alphabet sizes, J. Combin. Des., 11 (2003), 413-432. https://doi.org/10.1002/jcd.10059

[15] K. Meagher, B. Stevens, Covering arrays on graphs, J. Comb. Theory Ser. B, 95 (2005), 134-151. https://doi.org/10.1016/j.jctb.2005.03.005

[16] K. Meagher, L. Moura, L. Zekaoui, Mixed covering arrays on graphs, J. Comb. Des., 15 (2007), 393-404. https://doi.org/10.1002/jcd.20149

[17] P. Danziger, E. Mendelsohn, L. Moura, B. Stevens, Covering arrays avoiding forbidden edges, Theor. Comput. Sci., 410 (2009), 5403-5414. https://doi.org/10.1016/j.tcs.2009.07.057

[18] C. J. Colbourn, D. W. McClary, Locating and detecting arrays for interaction faults, J. Comb. Optim., 15 (2008), 17-48. https://doi.org/10.1007/s10878-007-9082-4

[19] C. M. Wang, C. Shi, T. Tsuchiya, Q. R. Zhang, Detecting arrays on graphs, Electron. Res. Arch., 33 (2025), 3328-3347. https://doi.org/10.3934/era.2025147

[20] C. Shi, L. Jiang, A. Y. Tao, Consecutive detecting arrays for interaction faults, Graphs Combin., 36 (2020), 1203-1218. https://doi.org/10.1007/s00373-020-02176-7

[21] C. Shi, A. Tao, Consecutive detecting arrays from m-sequence, IAENG Int. J. Appl. Math., 50 (2020), 80-86.

[22] Y. Tang, J. X. Yin, Detecting arrays and their optimality, Acta Math. Sin. Engl. Ser., 27 (2011), 2309-2318. https://doi.org/10.1007/s10114-011-0184-7

[23] C. Shi, Y. Tang, J. X. Yin, The equivalence between optimal detecting arrays and super-simple OAs, Des. Codes Cryptogr., 62 (2012), 131-142. https://doi.org/10.1007/s10623-011-9498-9

[24] C. Shi, Y. Tang, J. X. Yin, Optimum mixed level detecting arrays, Ann. Stat., 42 (2014), 1546-1563. https://doi.org/10.1214/14-AOS1228

[25] C. Shi, Optimum Super-simple mixed covering arrays of type a¹b^k−1 , Acta Math. Sin. Engl. Ser., 33 (2017), 153-164. https://doi.org/10.1002/jcd.21657

[26] J. B. Liu, X. Wang, L. Hua, J. D. Cao, L. P. Chen, The coherence and robustness analysis for a family of unbalanced networks, IEEE Trans. Signal Inf. Process. Netw., 11 (2025), 378-387. https://doi.org/10.1109/tsipn.2025.3555164

[27] J. B. Liu, L. Guan, J. D. Cao, Property analysis and coherence dynamics for tree-symmetric networks with noise disturbance, J. Complex Netw., 12 (2024), 475-505. https://doi.org/10.1093/comnet/cnae029

[28] R. El-Shanawany, A. El-Mesady, S. M. Shaaban, Mutually orthogonal graph squares for disjoint union of paths, Appl. Math. Sci., 12 (2018), 303-310. https://doi.org/10.1155/2022/9308708