IEEE Transactions on Reliability · 1994 · 30 citations · 18 references
ComputingComputer ScienceAlgorithmsComputer NetworksOptimizationCombinatorial OptimizationGraph AlgorithmsGraph LabelingGraph TheoryNetwork OptimizationRouting AlgorithmsMinimum CutRecursive Algorithm DesignShortest Path ProblemsShortest Path Routing
This paper presents a new recursive labelling algorithm for determining all minimal cutsets in a directed network, using an approach adapted from dynamic programming algorithms for the classical shortest route problem. The algorithm produces all minimal cutsets, and uses comparison logic to eliminate any redundant cutsets. Computational experience shows that: (1) the time per cutset varies linearly with the number of nodes but decreases exponentially with the density of the graph; and (2) whereas the algorithm's performance with regard to 'change in the time per cutset vs. the number of nodes' is similar to other algorithms, it appears to exhibit superior performance where the time/cutset is compared to the density of the graph.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
18
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
S. Tsukiyama, Isao Shirakawa, Hiroshi Ozaki et al. · Journal of the ACM · 1980 · 102 citations · Full text