The implementation and analysis of parallel algorithm for finding perfect matching in the bipartite graphs
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:
PDFDOI: 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
This work is licensed under a Creative Commons Attribution 4.0 International License.