Title :
On Two Problems in the Generation of Program Test Paths
Author :
Gabow, Harold N. ; Maheshwari, Shachindra N. ; Osterweil, Leon J.
Author_Institution :
Department of Computer Science, University of Colorado
Abstract :
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.
Keywords :
Algorithmic complexity; NP-complete; constrained test paths; impossible pairs; program test paths; Algorithm design and analysis; Automatic testing; Buildings; Computer science; Flow graphs; Helium; Software engineering; Algorithmic complexity; NP-complete; constrained test paths; impossible pairs; program test paths;
Journal_Title :
Software Engineering, IEEE Transactions on
DOI :
10.1109/TSE.1976.233819
