On structured digraphs and program testing
- 1 January 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-30 (1) , 67-77
- https://doi.org/10.1109/TC.1981.6312158
Abstract
Certain graph theoretic problems dealing with the testing of structured programs are treated. A structured digraph is a digraph that represents a structured program. A labelling procedure which characterizes structured digraphs is described. An efficient algorithm for finding a minimum path cover for the vertices of digraphs that belong to an important family of structured digraphs is given. To model interactions among code segments the notions of `required pairs' and `must pairs' are introduced and the corresponding constrained path cover problems are shown to be NP-complete even for acyclic structured digraphs.Keywords
This publication has 0 references indexed in Scilit: