Parallel implementation of the k-connectivity test algorithm

Przemysław Sokołowski, Paweł Konieczka, Jakub Sochacki, Marcin Paprzycki


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.

Full Text:


Data publikacji: 2015-01-04 00:00:00
Data złożenia artykułu: 2016-04-27 10:11:08


Total abstract view - 273
Downloads (from 2020-06-17) - PDF - 0



  • There are currently no refbacks.

Copyright (c) 2015 Annales UMCS Sectio AI Informatica

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.