Improved serial algorithms for mutation analysis

Abstract

Existing serial algorithms to do mutation analysis are inefficient, and descriptions of parallel mutation systems pre-suppose that these serial algorithms are the best one can do serially. We present a universal mutation analysis data structure and new serial algorithms for both strong and weak mutation analysis that on average should perform much faster than existing ones, and can never do worse. We describe these algorithms as well as the results of our analysis of their run time complexities. We believe that this is the first paper in which analytical methods have been applied to obtain the run time complexities of mutation analysis algorithms.