Mixed covering arrays on graphs and tabu search algorithms

Abstract

Covering arrays are combinatorial objects that have been successfully applied in the design of test suits for testing software, networks and circuits. Mixed covering arrays on graphs are new generalizations of both mixed covering arrays and covering arrays on graphs. In this thesis, we give new theoretical results and constructions for mixed covering arrays on graphs. First, we extend to the mixed case the work done by Meagher and Stevens [31], which uses graph homomorphisms for covering arrays on graphs. Second, we study covering arrays on special classes of graphs. In particular, we solve to optimality the case in which G is a tree, a cycle or a bipartite graph, as well as give results for wheels and cubic graphs. We also provide general graph operations that preserve the size of a balanced covering array. In the second part of the thesis, we do a complete experimental study of two tabu search algorithms for covering array construction. POT is a variation of the algorithm given by Stardom [40] while PAT is an implementation of the algorithm proposed by Nurmela [35]. We conclude that they provide effective methods for constructing covering arrays of moderate size. In particular, POT and PAT improve upper bounds for 18 sets of parameters for covering arrays.