Calculating Prioritized Interaction Test Sets with
Constraints using Binary Decision Diagrams
Link to original publication 
Download Bibtex entry
Salecker and Robert Reicherdt and Sabine Glesner
Int’l Workshop on Variability-intensive Systems Testing, Validation
& Verification (ICST-VAST2011)
||Combinatorial interaction testing has become an established
systematically determine test sets for highly-configurable software
systems. The generation of minimal test sets that fulfill the demanded
criteria is an NP-complete problem.
Constraint handling and integrated test case prioritization, features
for practical use, further complicate the problem.
We present a novel algorithm that exploits our observation that
the combinatorial interaction testing problem with constraints can
be modelled as a single propositional logic formula.
Our test set calculation algorithm uses binary decision diagrams as
efficient data structure for this formula.
The algorithm supports constraints and prioritization. Our evaluation
results prove its cost effectiveness. For many benchmark problems the
algorithm calculates the best results compared to other greedy