Improved covering arrays using covering perfect hash families with groups of restricted entries

摘要

Covering perfect hash families (CPHFs) are used to represent compactly some covering arrays. For CPHFs there is an efficient way to determine if the covering arrays derived from them are or not complete covering arrays; and this characteristic eases the construction of large covering arrays by greedy and metaheuristic methods working over the CPHF representation. CPHFs has been constructed in other works by backtracking, tabu search, simulated annealing, and greedy methods. The present work introduces a new simulated annealing algorithm that is able to construct CPHFs with groups of rows with restricted entries. In a CPHF of this kind the entries have some dependencies among them, that is, the values in some rows restrict the values that can appear in other rows. Restricted CPHFs produce covering arrays smaller than the ones derived from CPHFs without restricted entries. By using the new simulated annealing algorithm, we construct 135 new CPHFs whose derived covering arrays improve the upper bound of 19,669 covering array numbers.