Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Improving IPOG’s Vertical Growth Based on a Graph Coloring Scheme

Published

Author(s)

Raghu N. Kacker, David R. Kuhn, Yu Lei

Abstract

In this paper, we show that the vertical growth phase of IPOG is optimal for t-way test generation when t = 2, but it is no longer optimal when t is greater than 2. We present an improvement that reduces the number of tests generated during vertical growth. The vertical growth problem is modeled as a classical NP-hard problem called "Minimum Vertex Coloring." We adopt a greedy coloring algorithm to determine the order in which missing tuples are covered during vertical growth. We implemented a revised IPOG algorithm incorporating this improvement. The experimental results show that compared with the original IPOG algorithm, which uses an arbitrary order to cover missing tuples during vertical growth, the revised IPOG algorithm reduces the number of tests for many real-life systems.
Proceedings Title
Proceedings of
Seventh IEEE International Conference on Software Testing, Verification and Validation
ICST 2015
Conference Dates
April 13-17, 2015
Conference Location
Graz
Conference Title
Seventh IEEE International Conference on Software Testing, Verification and Validation
ICST 2015

Keywords

Combinatorial testing, Multi-way test generation, ACTS, Minimum vertex coloring, Tuple ordering

Citation

Kacker, R. , Kuhn, D. and Lei, Y. (2015), Improving IPOG’s Vertical Growth Based on a Graph Coloring Scheme, Proceedings of Seventh IEEE International Conference on Software Testing, Verification and Validation ICST 2015, Graz, -1, [online], https://doi.org/10.1109/ICSTW.2015.7107444 (Accessed April 13, 2024)
Created April 12, 2015, Updated September 21, 2020