Istituto di Scienza e Tecnologie dell'Informazione     
Martelli A. An application of regular algebra to the enumeration of cut sets in a graph. Internal note IEI-B73-20, 1973.
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.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional