Abstract
Test coverage criteria define a set of entities of a program flowgraph and
require that every entity is covered by some test. In this paper we first indentify
E(c), the set of entities to be covered according to a criterion (c), for a family
of widely used test coverage criteria. We then present a method to derive a minimum
set of entities, called a spanning set, such that a set of test paths covering
the entities in this set covers every entity in E(c). We provide a generalised
algorithm, which is parametrized by the coverage criterion. We suggest several
useful applications of spanning sets of entities to testing. In particular, they
help to reduce and to estimate the number of tests needed to satisfy test coverage
criteria.