On Path Cover Problems in Digraphs and Applications to Program Testing
- 1 September 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-5 (5) , 520-529
- https://doi.org/10.1109/tse.1979.234213
Abstract
In this paper various path cover problems, arising in program testing, are discussed. Dilworth's theorem for acyclic digraphs is generalized. Two methods for fmding a minimum set of paths (minimum path cover) that covers the vertices (or the edges) of a digraph are given. To model interactions among code segments, the notions of required pairs and required paths are introduced. It is shown that rmding a minimum path cover for a set of required pairs is NP-hard. An efficient algorithm is given for findng a minimum path cover for a set of required paths. Other constrained path problems are contsidered and their complexities are discussed.Keywords
This publication has 9 references indexed in Scilit:
- Computational Complexity of Combinatorial and Graph-Theoretic ProblemsPublished by Springer Nature ,2011
- Data Flow Analysis in Software ReliabilityACM Computing Surveys, 1976
- On Two Problems in the Generation of Program Test PathsIEEE Transactions on Software Engineering, 1976
- Program graphs, an algebra, and their implication for programmingIEEE Transactions on Software Engineering, 1975
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Efficient determination of the transitive closure of a directed graphInformation Processing Letters, 1971
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- A Decomposition Theorem for Partially Ordered SetsAnnals of Mathematics, 1950