Martelli A. An application of regular algebra to the enumeration of cut sets in a graph. In: Information processing 74 : proceedings of IFIP congress 74, Stockholm, Sweden, August 5-10, 1974., pp. 511 - 515. Jack L. Rosenfeld (editor). North-Holland, 1974. |

Abstract (English) |
Many path-finding problems have been formulated in a suitable algebra and, in terms of this algebra, they have been reduced to the solution of a system of linear equations. In this paper, these results are extended to the problem of enumerating all minimal i-j cut sets between all pairs of nodes in a directed graph. An i-j cut set is a set of arcs such that, by removing these arcs, there is no path from node i to node j. A definition of sum and multiplication is given, in such a way that the problem can be represented by a system of linear equations. Gaussian elimination provides an efficient solution of this system. | |

Subject |

1) Download Document PDF |

Open access Restricted Private