VERTEX CUTSETS OF UNDIRECTED GRAPHS

This paper deals with the enumeration of all minimal s-t vertex cutset s separating two vertices (source & terminal) in an undirected graph, The problem is handled by direct-enumeration based on a necessary & su fficient condition for a set of vertices to be a minimal vertex cutset , The algorithm thus does not enumerate paths or basic paths as a firs t step. This approach has yielded an algorithm which generates minimal vertex cutsets at O(e . n) {where e,n = number of (edges, vertices) i n the graph} computational effort per vertex cutset. Formal proofs of the algorithm and its complexity are presented, Results of some comput ational experience show that, a) this algorithm is appreciably faster than previous algorithms, and b) can handle much larger graphs due to less memory requirements, The number of vertex cutsets does not exceed ((gilb(1/2(n - 2))(n - 2))+2.