A novel and efficient algorithm for scanning all minimal cutsets of a graph

Details A novel and efficient algorithm for scanning all minimal cutsets of a graph A novel and efficient algorithm for scanning all minimal cutsets of a graph

2002-11-27

arxiv.org/abs/math/0211436v1

Mathematics

Combinatorics

15 pages, 15 figures, submitted to the Journal of the ACM

Scientific paper

We propose a novel algorithm for enumerating and listing all minimal cutsets of a given graph. It is known that this problem is NP-hard. We use connectivity properties of a given graph to develop an algorithm with reduced complexity for finding all its cutsets. We use breadth first search (BFS) method in conjunction with edge contraction to develop the algorithm. We introduce the concepts of a pivot vertex and absorbable clusters and use them to develop an enhanced recursive contraction algorithm. The complexity of the proposed algorithm is proportionate to the number of cutsets. We present simulation results to compare the performance of our proposed algorithm with those of existing methods.

Affiliated with

Also associated with

No associations

Rating

A novel and efficient algorithm for scanning all minimal cutsets of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A novel and efficient algorithm for scanning all minimal cutsets of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A novel and efficient algorithm for scanning all minimal cutsets of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-420028