Algorithms for parallel k -vertex connectivity and sparse certificates
Joseph Cheriyan, Ramakrishna Thurimella · 1991
A certificatefor the k-vertex connectivity of a graph G = (V, E) is a subset E' of E such thatLet n = IV[ and m = IEI.A certificate is called sparse if it has size lE'I = O(kn).We show that sparse certificates for undirected graphs can be computed by executing k breadth first searches in sequence.This directly gives an efficient algorithm on the distributed model of computation.Using certificates of size O(k2 n), we show that the k-vertex connectivity of an undirected graph can be tested on the CRCW PRAM model in a parallel running time of O(k2 log n) using k3n2cr(k2n, n)/(log n) processors.For k >3 and m > k2n, this improves on previous deterministic parallel algorithms (for dense graphs and for constant k >4 the number of processors improves by a factor of roughly n).We also give sequential algorithms for finding (undirected) sparse certificates '(on-line", and for finding -.certificate es of size <2 k2 n for directed graphs,