Martelli A. An application of regular algebra to the enumeration of cut sets in a graph. Internal note IEI-B73-20, 1973. |

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 papaer, these results are extended to the problem od 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 proble can be presented by a system of linear equations. Gaussian elimination provides an efficient solution of this system. | |

Subject |

1) Download Document PDF |

Open access Restricted Private