Parallel implementation of the k-connectivity test algorithm

Abstract

There exists a large number of theoretical results concerning fast parallel algorithms for graph problems, however, scarcely one finds reports of their practical implementation. In an attempt at partial filling this gap we discuss implementation of an algorithm performing the pretest for k-connectivity. This test is based, first, on the Scan-First Search algorithm introduced in [1]. Utilizing this procedure we decrease the size of the input graph by removing selected edges so that the resulting graph (certificate of k-connectivity) has only 0(kn) left. During this part of computations we can answer the question about k-connectivity negatively if a certificate cannot be generated. Afterwards, we can apply the test described in [2] to establish ^-connectivity in the remaining cases.