Name
Abstract | ||
|---|---|---|
In this paper we consider the problem of finding a legal source to sink (s-t) path in a digraph G = (V, E), for which a set of impossible paths is specified. This problem arises in program testing. An efficient algorithm is presented for the case when G is an acyclic digraph and the general problem is shown to be computationally intractable. |
Year | DOI | Venue |
|---|---|---|
1984 | 10.1016/0020-0190(84)90030-9 | Information Processing Letters |
Keywords | Field | DocType |
Program testing,impossible path,legal path,NP-completeness | Discrete mathematics,Combinatorics,Shortest path problem,Longest path problem,Program testing,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
18 | 2 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heung-soon Ihm | 1 | 0 | 0.34 |
| Simeon C. Ntafos | 2 | 599 | 98.18 |