Martelli A. A gaussian elimination algorithm for the enumeration of cut sets in a graph. In: Journal of the ACM, vol. 23 (1) pp. 58 - 73. 1975. |

Abstract (English) |
By defining a suitable algebra for cut sets, it is possible to reduce the problem of enumerating the cut sets between all pairs of nodes in a graph to the problem of solving a system of linear equations. An algorithm for solving this system using Gaussian elimination is presented in this paper. The efficiency of the algorithm depends on the implementation of sum and multiplication. Therefore, some proprieties of cut sets are investigated, which greatly simplify the implementation of these operations for the case of undirected graphs. The time required by the algorithm is shown to be linear with tyhe number of cut sets for complete graphs. Some experimental results are given, proving that the efficiency of the algorithm increases by increasing the numbger of pairs of nodes for which the cut sets are computed. | |

Subject | Graph teory Gaussian elimination |

1) Download Document PDF |

Open access Restricted Private