Improving IPOG's vertical growth based on a graph coloring scheme
Feng Duan, Yu Lei, Linbin Yu, Raghu N. Kacker, D. Richard Kuhn · 2015
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 adopted 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.