On Two Problems in the Generation of Program Test Paths
Harold N. Gabow, S.N. Maheshwari, Leon J. Osterweil · IEEE Transactions on Software Engineering · 1976
In this paper we analyze the complexity of algorithms for two problems that arise in automatic test path generation for programs: the problem of building a path through a specified set of program statements and the problem of building a path which satisfies impossible-pairs restrictions on statement pairs. These problems are both reduced to graph traversal problems. We give an efficient algorithm for the first, and show that the second is NP-complete.