Finding all minimum‐size separating vertex sets in a graph
Arkady Kanevsky · Networks · 1993
Abstract 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(2kn3) 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(log2 n) randomized time using Θ(;M2n2 + knNα) = O(4k(n6/k2)) 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.