Parallel implementation of the k-connectivity test algorithm

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

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.17951/ai.2004.2.1.91-99
Data publikacji: 2015-01-04 00:00:00
Data złożenia artykułu: 2016-04-27 10:11:08


Statistics


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

Indicators



Refbacks

  • 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.