Parallel maximum flow solver for multi-core machines
Loading...
Date
2010.
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2010.
Abstract
We provide a parallel algorithm for calculating maximum flow between two nodes, in a capacitated network. The algorithm we propose is based on push-relabel algorithm due to Goldberg and uses a modified first in first out selection strategy together with global relabeling heuristic. Our implementation targets multi-core processors, implements task stealing to balance load between multiple threads of execution and uses fast atomic variables for synchronization instead of costly general purpose locks. We compare our algorithm to other push-relabel based algorithms and demonstrate that it performs well in practice.