Document Type

Technical Report

Publication Date

Fall 9-1-1975


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 flow graph nodes and the problem of building a path which satisfies impossible-pairs restrictions in a flow graph. We give a highly efficient algorithm for the first problem, and show that the second problem is NO-complete in the sense of Cook and Karp.