Thumbnail
Access Restriction
Subscribed

Author Boesch, F. T. ♦ Gimpel, J. F.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1977
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A point-disjoint path cover of a directed graph is a collection of point-disjoint paths (some paths possibly having zero length) which covers all the points. A path cover which minimizes the number of paths corresponds to an optimal sequence of the steps of a computer program for efficient coding and documentation. The minimization problem for the general directed graph is hard in the sense of being NP-complete. In the case of cycle-free digraphs, however, the problem is polynomial, for it is shown that it can be reduced to the maximum-matching problem. A heuristic given here for finding a near optimal path cover for the general case is based upon applying the maximum-matching algorithm to the subgraphs of an interval decomposition.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1977-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 24
Issue Number 2
Page Count 7
Starting Page 192
Ending Page 198


Open content in new tab

   Open content in new tab
Source: ACM Digital Library