Ahmad, S. Hasanuddin Simple enumeration of minimal cutsets of acyclic directed graph. (English) Zbl 0664.90030 IEEE Trans. Reliab. 37, No. 5, 484-487 (1988). There are many methods to enumerate cutsets of an acyclic directed graph. All of these involve advanced mathematics. This paper gives 2 methods which use combinations of nodes to enumerate all minimal cutsets. One simply has to enumerate all combinations of orders 1 to N-3 of nodes from 2 to N-1, where N is the total number of nodes. Collecting only those symbols of links of the first row of the adjacency matrix and in the rows given in a combination which are not in the columns of the combination a cutset of an acyclic directed graph, having all adjacent nodes, is obtained. To obtain the cutsets of a general acyclic directed graph, four rules are given for deletion of those combinations which yield redundant and nonminimal cutsets. These rules provide a reduced set of combinations which then gives rise to minimal cutsets of a general graph. Three examples illustrate the algorithms. Cited in 2 Documents MSC: 90B10 Deterministic network models in operations research 90C35 Programming involving graphs or networks 68R10 Graph theory (including graph drawing) in computer science 90B25 Reliability, availability, maintenance, inspection in operations research Keywords:reliability of networks; cutsets; acyclic directed graph PDFBibTeX XMLCite \textit{S. H. Ahmad}, IEEE Trans. Reliab. 37, No. 5, 484--487 (1988; Zbl 0664.90030) Full Text: DOI