Parallel implematation of flow and matching algorithms
Jagiellonian University, Krakow
arXiv:1110.6231v1 [cs.DC] (28 Oct 2011)
@article{2011arXiv1110.6231L,
author={L}upi{‘n}ska}, A.},
title={"{Parallel implematation of flow and matching algorithms}"},
journal={ArXiv e-prints},
archivePrefix={"arXiv"},
eprint={1110.6231},
primaryClass={"cs.DC"},
keywords={Computer Science – Distributed, Parallel, and Cluster Computing},
year={2011},
month={oct},
adsurl={http://adsabs.harvard.edu/abs/2011arXiv1110.6231L},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
In our work we present two parallel algorithms and their lock-free implementations using a popular GPU environment Nvidia CUDA. The first algorithm is the push-relabel method for the flow problem in grid graphs. The second is the cost scaling algorithm for the assignment problem in complete bipartite graphs.
October 31, 2011 by hgpu
