| تعداد نشریات | 24 |
| تعداد شمارهها | 851 |
| تعداد مقالات | 7,575 |
| تعداد مشاهده مقاله | 13,413,633 |
| تعداد دریافت فایل اصل مقاله | 11,580,411 |
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 اصل مقاله (134.61 K) | ||
| شناسه دیجیتال (DOI): 10.22099/ijste.2006.879 | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Breadth first search (BFS)؛ cutset scanning؛ edge contraction؛ minimal edge cutset؛ #P-complete | ||
|
آمار تعداد مشاهده مقاله: 1,422 تعداد دریافت فایل اصل مقاله: 1,188 |
||