Covering Arrays
Introduction
This web page aims at reporting the main results produced during the project No. 099276, entitled "Algorithms for the canonization of Covering Arrays" (20102014), funded by the CONACyT Mexico.
The main objective of this project was designing and implementing efficient algorithms, both exact and approximate ones, for the canonization of Covering Arrays (CA's).
A covering array, CA(N; t, k, v), of size N, strength t, degree k, and order v is an N × k array on v symbols such that every N × t subarray includes, at least once, all the ordered subsets from v symbols of size t (ttuples). The minimum N for which a CA(N; t, k, v) exists is the covering array number and it is defined according to the following equation.
CAN(t, k, v) = min{N : ∃ CA(N; t, k, v)}
Finding the covering array number is also known in the literature as the Covering Array Construction (CAC) problem. It is equivalent to the problem of maximizing the degree k of a covering array given the values N, t, and v. Addressing this problem in reasonable time has been the focus of much research.
Relevant publications
New Bounds for Binary Covering Arrays Using Simulated Annealing.
Jose TorresJimenez and Eduardo RodriguezTello,
Information Sciences, 185(1):137152, Elsevier February 2012.



Simulated Annealing for Constructing Binary Covering Arrays of
Variable Strength.
Jose TorresJimenez and Eduardo RodriguezTello,
Proceedings of the IEEE CEC 2010, Barcelona Spain,
pp. 41024109, IEEE Press 2010.



Memetic Algorithms for Constructing Binary Covering Arrays of Strength Three.
Eduardo RodriguezTello and Jose TorresJimenez,
Proceedings of the EA 2009, Strasbourg France,
Lecture Notes in Computer Science, 5975:8697, Springer 2010.
2nd place Best Paper Award



A New Backtracking Algorithm for Constructing Binary Covering Arrays of Variable Strength.
Josue BrachoRios, Jose TorresJimenez and Eduardo RodriguezTello,
Proceedings of the MICAI 2009, Guanajuato, México,
Lecture Notes in Artificial Intelligence, 5845:397407, Springer 2009.



Strength Two Covering Arrays Construction Using a SAT Representation.
Daniel LopezEscogido, Jose TorresJimenez, Eduardo RodriguezTello and Nelson RangelValdez,
Proceedings of the MICAI 2008, Edo. Méx. México,
Lecture Notes in Artificial Intelligence, 5317:4453, Springer 2008.



Use of Covering Arrays for tunning metaheuristics
Maximum Parsimony Phylogenetic Inference Using Simulated Annealing.
JeanMichel Richer, Eduardo RodriguezTello and Karla E. VazquezOrtiz,
Proceedings of the EVOLVE 2012, Mexico City, Mexico,
Advances in Intelligent and Soft Computing, 175:189203, Springer 2012.



An Improved Memetic Algorithm for the Antibandwidth Problem.
Eduardo RodriguezTello and Luis Carlos Betancourt,
Proceedings of the EA 2011, Angers France,
Lecture Notes in Computer Science, 7401:120132, Springer 2012.



Request for information
If you are interested in finding out more information about the Covering Arrays generated during this research project, please fill out the form below.