Affordable Access

Publisher Website

Covering arrays avoiding forbidden edges

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
410
Issue
52
Identifiers
DOI: 10.1016/j.tcs.2009.07.057
Disciplines
  • Computer Science

Abstract

Abstract Covering arrays (CAs) can be used to detect the existence of faulty pairwise interactions between parameters or components in a software system. The generalization considered here applies to the situation in which some input combinations are invalid, a requirement quite common in software testing. In this paper, we study covering arrays avoiding forbidden edges ( C A F E s), where certain pairwise interactions are forbidden while all others must be covered, and we aim to minimize the number of tests. We establish a theoretical framework for this problem, by providing connections to the edge clique covering problem, lower and upper bounds, complexity results and a recursive construction. We also give an algorithm for the case of binary alphabets.

There are no comments yet on this publication. Be the first to share your thoughts.