Finding all minimum‐size separating vertex sets in a graph

We present a new algorithm based upon network flows for finding all minimum‐size separating vertex sets in an undirected and unweighted graph. The sequential implementation of our algorithm runs in Θ( Mn + C ) = O (2 k n 3 ) time, where M is the number of minimum‐size separating vertex sets of the graph; n , the number of the vertices in the graph; m , the number of the edges in the graph; k , the connectivity of the graph, and C = kn min( k ( m + n ), A ), where A is the complexity of the best maximum flow algorithm for unit networks. The parallel implementation runs either in O ( k log n ) deterministic time or in O (log 2 n ) randomized time using Θ(; M 2 n 2 + knN α ) = O (4 k ( n 6 / k 2 )) processors on a PRAM, where N α is the number of processors needed for parallel matrix multiplication in O (log n ) time on PRAM. © 1993 by John Wiley & Sons, Inc.