One-test-at-a-time heuristic search for interaction test suites

Renée C. Bryce, Charles Colbourn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

80 Scopus citations


Algorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples associated with higher strength hinders the efficacy of interaction testing. Test suites are inherently large, so testers may not run entire test suites. To address these problems, we combine a simple greedy algorithmallwith heuristic search to construct and dispense one test at a time. Our algorithm attempts to maximize the number of t-tuples covered by the earliest tests so that if a tester only runs a partial test suite, they test as many t-tuples as possible.allHeuristic search is shown to provide effective methods for achieving such coverage.

Original languageEnglish (US)
Title of host publicationProceedings of GECCO 2007
Subtitle of host publicationGenetic and Evolutionary Computation Conference
Number of pages8
StatePublished - 2007
Event9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007 - London, United Kingdom
Duration: Jul 7 2007Jul 11 2007

Publication series

NameProceedings of GECCO 2007: Genetic and Evolutionary Computation Conference


Other9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007
Country/TerritoryUnited Kingdom


  • Covering arrays
  • Great flood
  • Heuristic search
  • Hill climbing
  • Simulated annealing
  • Software interaction testing
  • T-way interaction testing
  • Tabu search
  • Test suite prioritization

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Theoretical Computer Science


Dive into the research topics of 'One-test-at-a-time heuristic search for interaction test suites'. Together they form a unique fingerprint.

Cite this