A graph‐based postoptimization approach for covering arrays

Abstract

AbstractCovering arrays (CAs) are combinatorial objects with interesting features that have practical applications such as experimental design and fault detection in hardware and software. We introduce a graph‐based postoptimization (GBPO) approach to reduce the size of CAs exploiting the redundancy in CAs previously constructed. To evidence the advantages of using GBPO, we have instantiated it with 2 sets of CAs: (1) 560 CAs of strength 2≤t≤6, alphabet 2≤v≤6, and parameters 3≤k≤32 generated by an optimized version of In‐Parameter‐Order‐Generalized (IPOG‐F) and GBPO improved all CAs, and 37 cases matched the best‐known upper bounds; and (2) 32 CAs of strengtht=2, alphabet 3≤v≤6, and number of parameters 8≤k≤146; in this set, 16 cases were improved, and 16 cases were matched.