×

Simple enumeration of minimal cutsets of acyclic directed graph. (English) Zbl 0664.90030

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.

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
PDFBibTeX XMLCite
Full Text: DOI