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

Published

April 13, 2015

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

Pub Type

Conferences

Download Paper

https://doi.org/10.1109/ICSTW.2015.7107444

Local Download

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 May 10, 2024)