RECURSIVE CONTRACTION ALGORITHM: A NOVEL AND EFFICIENT GRAPH TRAVERSAL METHOD FOR SCANNING ALL MINIMAL CUT SETS
Ahmad R. Sharafat, Omid Reza Marouzi · 2006
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.