The implementation and analysis of parallel algorithm for finding perfect matching in the bipartite graphs

Maciej Chróśniak, Jakub Dworniczak, Karol Ziarko, Marcin Paprzycki

Abstract


There exists a large number of theoretical results concerning parallel algorithms for the graph problems. One of them is an algorithm for the perfect matching problem, which is also the central part of the algorithm for finding a maximum flow in a net. We have attempted at implementing it on a parallel computer with 12 processors (instead of the theoretical 0(n^3.5m) processors). When pursuing this goal we have run into a number of practical problems. The aim of this paper is to discuss them as well as the experimental results of our implementation.

Full Text:

PDF


DOI: http://dx.doi.org/10.17951/ai.2004.2.1.81-89
Date of publication: 2015-01-04 00:00:00
Date of submission: 2016-04-27 10:11:07


Statistics


Total abstract view - 435
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.