 Improved covering arrays using covering perfect hash families with groups of restricted entriesJose Torres-Jimenez and Idelfonso Izquierdo-Marquez Applied Mathematics and Computation, 2020, vol. 369, issue C Abstract: 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. Keywords: Covering perfect hash families; Covering arrays; Restricted CPHFs; Simulated annealing (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:369:y:2020:i:c:s0096300319308185 DOI: 10.1016/j.amc.2019.124826 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.