Recursive contraction algorithm: a novel and efficient graph traversal method for scanning all minimal cut sets
Editorial
10.22099/ijste.2006.879
Abstract
We propose a novel algorithm called RCA_MC, in which we use the breadth first search method (BFS) in conjunction with edge contraction and connectivity properties of a given undirected graph to enumerate and scan all its minimal edge cutsets. It is known that the problem of enumerating all minimal edge cutsets of a given graph is #P-complete. In addition, we introduce the concepts of pivot vertex and absorbable clusters, and use them to develop our enhanced recursive contraction for scanning all mimimal edge cutsets, called ERCA_MC, of a given graph. Simulation results provide empirical evidence that the complexity of the ERCA_MC algorithm is linear per cutset.
(2006). Recursive contraction algorithm: a novel and efficient graph traversal method for scanning all minimal cut sets. Iranian Journal of Science and Technology Transactions of Electrical Engineering, 30(6), 749-761. doi: 10.22099/ijste.2006.879
MLA
. "Recursive contraction algorithm: a novel and efficient graph traversal method for scanning all minimal cut sets", Iranian Journal of Science and Technology Transactions of Electrical Engineering, 30, 6, 2006, 749-761. doi: 10.22099/ijste.2006.879
HARVARD
(2006). 'Recursive contraction algorithm: a novel and efficient graph traversal method for scanning all minimal cut sets', Iranian Journal of Science and Technology Transactions of Electrical Engineering, 30(6), pp. 749-761. doi: 10.22099/ijste.2006.879
VANCOUVER
Recursive contraction algorithm: a novel and efficient graph traversal method for scanning all minimal cut sets. Iranian Journal of Science and Technology Transactions of Electrical Engineering, 2006; 30(6): 749-761. doi: 10.22099/ijste.2006.879
)