On Two Problems in the Generation of Program Test Paths
On Two Problems in the Generation of Program Test Paths
复制标题
程序测试路径生成中的两个问题的探讨
DOI：
--
复制
发表时间：
1976
影响因子：
7.4
通讯作者：
L. Osterweil
中科院分区：
文献类型：
--
作者：
H. Gabow;Shachindra N. Maheswari;L. Osterweil
在本文中，我们分析了针对程序的自动测试路径生成中出现的两个问题的算法的复杂性：通过指定的程序语句构建路径的问题，以及建立满足不可能对语句限制的路径的问题成对。这些问题都降低为图形遍历问题。我们为第一个提供了有效的算法，并证明第二个是NP完整的。
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.